home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _dfsnum.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  1.6 KB  |  59 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _dfsnum.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  DFS_NUM (depth first search numbering)                                      *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24. #include <LEDA/graph_alg.h>
  25.  
  26. int dfs_count1,dfs_count2;
  27.  
  28. void d_f_s(node v, node_array(bool)& S, node_array(int)& dfsnum, 
  29.                                         node_array(int)& compnum,
  30.                                         list(edge)& T )
  31. { node w;
  32.   edge e;
  33.  
  34.   S[v] = true;
  35.   dfsnum[v] = ++dfs_count1;
  36.  
  37.   forall_adj_edges(e,v) 
  38.     { w = target(e);
  39.       if (!S[w]) 
  40.        { T.append(e);
  41.          d_f_s(w,S,dfsnum,compnum,T);
  42.         }
  43.      }
  44.  
  45.   compnum[v] = ++dfs_count2;
  46. } 
  47.  
  48. list(edge) DFS_NUM(const graph& G, node_array(int)& dfsnum, 
  49.                                    node_array(int)& compnum)
  50. { 
  51.   list(edge) T;
  52.   node_array(bool) reached(G,false);
  53.   node v;
  54.   dfs_count1 = dfs_count2 = 0;
  55.   forall_nodes(v,G) if (!reached[v]) d_f_s(v,reached,dfsnum,compnum,T);
  56.   return T;
  57. }
  58.  
  59.