home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _compone.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  1.7 KB  |  75 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _components.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. *  COMPONENTS  (connected components)                                          *
  19. *                                                                              *
  20. *******************************************************************************/
  21.  
  22.  
  23.  
  24. #include <LEDA/graph_alg.h>
  25.  
  26. #include <LEDA/node_partition.h>
  27.  
  28.  
  29. int COMPONENTS(const ugraph& G, node_array(int)& compnum)
  30. { // computes connected components of undirected graph G
  31.   // compnum[v] = i  iff v in component i
  32.   // number of components is returned
  33.  
  34.   node v,w;
  35.   list(node) S;
  36.   int count = 0;
  37.  
  38.   node_array(bool) reached(G,false);
  39.  
  40.   forall_nodes(v,G) 
  41.      if (!reached[v]) 
  42.       { S = DFS(G,v,reached);
  43.         forall(w,S) compnum[w] = count;
  44.         count++; 
  45.        }
  46.  
  47.   return count;
  48. }
  49.  
  50.  
  51.  
  52. int COMPONENTS1(const ugraph& G, node_array(int)& compnum)
  53. { 
  54.  
  55.   node_partition P(G);
  56.   edge e;
  57.   node v;
  58.  
  59.   forall_nodes(v,G) compnum[v] = 0;
  60.  
  61.   forall_edges(e,G) P.union_blocks(source(e),target(e));
  62.  
  63.   int count = 0;
  64.   forall_nodes(v,G) 
  65.    { node w = P.find(v);
  66.      if (compnum[w]==0) compnum[w] = ++count;
  67.     }
  68.  
  69.   forall_nodes(v,G) compnum[v] = compnum[P.find(v)];
  70.  
  71.   return count;
  72. }
  73.  
  74.  
  75.