/*******************************************************************************
+
+  LEDA 3.5
+
+  _dfsnum.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/

//------------------------------------------------------------------------------
// Depth First Search Numbering 
//                                                                              
// S. N"aher (1989)
//------------------------------------------------------------------------------


#include <LEDA/graph_alg.h>

static int count1;
static int count2;

static void dfs(node v, node_array<int>& dfsnum, 
                        node_array<int>& compnum,
                        list<edge>& T )
{ dfsnum[v] = ++count1;

  edge e;
  forall_adj_edges(e,v) 
    { node w = target(e);
      if (dfsnum[w] == 0) 
       { T.append(e);
         dfs(w,dfsnum,compnum,T);
        }
     }

  compnum[v] = ++count2;
} 


list<edge> DFS_NUM(const graph& G, node_array<int>& dfsnum, 
                                   node_array<int>& compnum)
{ 
  list<edge> T;
  count1 = 0;
  count2 = 0;

  dfsnum.init(G,0);

  node v;
  forall_nodes(v,G) 
    if (dfsnum[v] == 0) 
      dfs(v,dfsnum,compnum,T);

  return T;
}

