home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _strongc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  3.4 KB  |  131 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _strongcomp.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. *  STRONG_COMPONENTS (strong connected components)                             *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25. #include <LEDA/graph_alg.h>
  26.  
  27. void scc_dfs(const graph& G, node v, node_array(int)& compnum,
  28.                                      node_array(int)& dfsnum,
  29.                                      list(node)&      unfinished,
  30.                                      list(node)&      roots,
  31.                                      node_array(bool)& in_unfinished,
  32.                                      int& count1, int& count2 );
  33.  
  34.  
  35. int STRONG_COMPONENTS(const graph& G, node_array(int)& compnum)
  36. {
  37.   // int STRONG_COMPONENTS(graph& G, node_array(int)& compnum)
  38.   // computes strong connected components (scc) of digraph G
  39.   // returns m = number of scc 
  40.   // returns in node_array(int) compnum for each node an integer with
  41.   // compnum[v] = compnum[w] iff v and w belong to the same scc
  42.   // 0 <= compnum[v] <= m-1 for all nodes v
  43.  
  44.   list(node)       unfinished;
  45.   list(node)       roots;
  46.   node_array(bool) in_unfinished(G,false);
  47.   node_array(int)  dfsnum(G,-1);
  48.  
  49.   int count1 = 0; 
  50.   int count2 = 0;
  51.  
  52.   node v;
  53.  
  54.   forall_nodes(v,G) 
  55.       if (dfsnum[v] == -1) 
  56.        scc_dfs(G,v,compnum,dfsnum,unfinished,roots,in_unfinished,count1,count2);
  57.  
  58.   return count2;
  59. }
  60.  
  61.  
  62. void scc_dfs(const graph& G, node v, node_array(int)& compnum,
  63.                                      node_array(int)& dfsnum,
  64.                                      list(node)&      unfinished,
  65.                                      list(node)&      roots,
  66.                                      node_array(bool)& in_unfinished,
  67.                                      int& count1, int& count2 )
  68. {
  69.   node w;
  70.  
  71.   dfsnum[v] = ++count1;
  72.   in_unfinished[v] = true;
  73.   unfinished.push(v);
  74.   roots.push(v);
  75.  
  76.   forall_adj_nodes(w,v)
  77.     { if (dfsnum[w]==-1) 
  78.        scc_dfs(G,w,compnum,dfsnum,unfinished,roots,in_unfinished,count1,count2);
  79.       else 
  80.        if (in_unfinished[w])
  81.         while (dfsnum[roots.head()]>dfsnum[w])  roots.pop();
  82.      }
  83.  
  84.   if (v==roots.head()) 
  85.    { do { w=unfinished.pop();
  86.           /* w is an element of the scc with root v */
  87.           in_unfinished[w] = false;
  88.           compnum[w] = count2;
  89.          } while (v!=w);
  90.      count2++;
  91.      roots.pop(); 
  92.     }
  93. }
  94.  
  95.  
  96. #include <LEDA/array.h>
  97.  
  98. declare(array,node)
  99.  
  100. int STRONG_COMPONENTS1(graph& G, node_array(int)& compnum)
  101. { 
  102.   node v,w;
  103.   int n = G.number_of_nodes();
  104.   int count = 0;
  105.  
  106.   array(node) V(1,n);
  107.   list(node) S;
  108.   node_array(int)  dfs_num(G), compl_num(G);
  109.   node_array(bool) reached(G,false);
  110.  
  111.   DFS_NUM(G,dfs_num,compl_num);
  112.  
  113.   forall_nodes(v,G) V[compl_num[v]] = v;
  114.  
  115.   G.rev();
  116.  
  117.  
  118.   int i;
  119.   for(i=n;i>0;i--)
  120.    { if ( !reached[V[i]] ) 
  121.       { S = DFS(G,V[i],reached);
  122.         forall(w,S) compnum[w] = count;
  123.         count++;
  124.        }
  125.     }
  126.  
  127.  return count;
  128.    
  129.  }
  130.  
  131.