home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _bicomp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.7 KB  |  99 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _bicomp.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. *  BICONNECTED COMPONENTS                                                      *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25. #include <LEDA/graph_alg.h>
  26.  
  27. declare(node_array,node)
  28.  
  29. void bcc_dfs(const ugraph& G, node v, node_array(int)&, 
  30.                                       node_array(int)&,
  31.                                       node_array(int)&,
  32.                                       node_array(node)&,
  33.                                       list(node)&,
  34.                                       int&,
  35.                                       int&);
  36.  
  37.  
  38. int BICONNECTED_COMPONENTS(const ugraph& G, node_array(int)& compnum)
  39. {
  40.   // computes the biconnected components of undirected graph G
  41.   // returns m = number of biconnected components
  42.   // returns in edge_array(int) compnum for each edge an integer with
  43.   // compnum[x] = compnum[y] iff x and y belong to the same component 
  44.   // 0 <= compnum[e] <= m-1 for all edges e
  45.  
  46.   list(node)       unfinished;
  47.   node_array(int)  dfsnum(G,-1);
  48.   node_array(int)  lowpt(G);
  49.   node_array(node) father(G);
  50.  
  51.   int count1 = 0; 
  52.   int count2 = 0;
  53.  
  54.   node v;
  55.  
  56.   forall_nodes(v,G) 
  57.       if (dfsnum[v] == (-1)) 
  58.        bcc_dfs(G,v,compnum,dfsnum,lowpt,father,unfinished,count1,count2);
  59.  
  60.   return count2;
  61. }
  62.  
  63.  
  64.  
  65. void bcc_dfs(const ugraph& G, node v, node_array(int)&  compnum,
  66.                               node_array(int)&  dfsnum,
  67.                               node_array(int)&  lowpt,
  68.                               node_array(node)& father,
  69.                               list(node)&       unfinished,
  70.                               int& count1, int& count2) 
  71. {
  72.   node w;
  73.  
  74.   dfsnum[v] = ++count1;
  75.  
  76.   lowpt[v] = dfsnum[v];
  77.  
  78.   unfinished.push(v);
  79.  
  80.   forall_adj_nodes(w,v)
  81.     if (dfsnum[w]==-1) 
  82.       { father[w] = v;
  83.         bcc_dfs(G,w,compnum,dfsnum,lowpt,father,unfinished,count1,count2);
  84.         lowpt[v] = Min(lowpt[v],lowpt[w]);
  85.        }
  86.     else lowpt[v] = Min(lowpt[v],dfsnum[w]);
  87.  
  88.  
  89.   if ((dfsnum[v] >= 2) && (lowpt[v] == dfsnum[father[v]]))
  90.    { do { w = unfinished.pop();
  91.           compnum[w] = count2;
  92.       } while (v!=w);
  93.  
  94.       count2++;
  95.     }
  96.  
  97. }
  98.  
  99.