开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_strongcomp.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：3k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_strongcomp.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _strongcomp.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. /*******************************************************************************
  15. *                                                                              *
  16. *  STRONG_COMPONENTS (strong connected components)                             *
  17. *                                                                              *
  18. *******************************************************************************/
  21. #include <LEDA/graph_alg.h>
  23. static void scc_dfs(const graph& G, node v, node_array<int>& compnum,
  24.                                             node_array<int>& dfsnum,
  25.                                             node_list& unfinished,
  26.                                             list<node>& roots,
  27.                                             int& count1, int& count2 );
  30. int STRONG_COMPONENTS(const graph& G, node_array<int>& compnum)
  31. {
  32.   // int STRONG_COMPONENTS(graph& G, node_array<int>& compnum)
  33.   // computes strong connected components (scc) of digraph G
  34.   // returns m = number of scc 
  35.   // returns in node_array<int> compnum for each node an integer with
  36.   // compnum[v] = compnum[w] iff v and w belong to the same scc
  37.   // 0 <= compnum[v] <= m-1 for all nodes v
  39.   list<node>     roots;
  40.   node_list      unfinished;
  41.   node_array<int> dfsnum(G,-1);
  43.   int count1 = 0; 
  44.   int count2 = 0;
  46.   node v;
  48.   forall_nodes(v,G) 
  49.       if (dfsnum[v] == -1) 
  50.        scc_dfs(G,v,compnum,dfsnum,unfinished,roots,count1,count2);
  52.   return count2;
  53. }
  56. static void scc_dfs(const graph& G, node v, node_array<int>& compnum,
  57.                                             node_array<int>& dfsnum,
  58.                                             node_list& unfinished,
  59.                                             list<node>& roots,
  60.                                             int& count1, int& count2 )
  61. {
  62.   node w;
  64.   dfsnum[v] = ++count1;
  65.   unfinished.push(v);
  66.   roots.push(v);
  68.   forall_adj_nodes(w,v)
  69.     { if (dfsnum[w]==-1) 
  70.        scc_dfs(G,w,compnum,dfsnum,unfinished,roots,count1,count2);
  71.       else 
  72.        if (unfinished(w))
  73.         while (dfsnum[roots.head()]>dfsnum[w])  roots.pop();
  74.      }
  76.   if (v==roots.head()) 
  77.    { do { w=unfinished.pop();
  78.           /* w is an element of the scc with root v */
  79.           compnum[w] = count2;
  80.          } while (v!=w);
  81.      count2++;
  82.      roots.pop(); 
  83.     }
  84. }
  88. int STRONG_COMPONENTS1(graph& G, node_array<int>& compnum)
  89. { 
  90.   node v,w;
  91.   int n = G.number_of_nodes();
  92.   int count = 0;
  94.   node* V = new node[n+1];
  96.   list<node> S;
  97.   node_array<int> dfs_num(G);
  98.   node_array<int> compl_num(G);
  99.   node_array<bool> reached(G,false);
  101.   DFS_NUM(G,dfs_num,compl_num);
  103.   forall_nodes(v,G) V[compl_num[v]] = v;
  105.   G.rev();
  107.   for(int i=n; i>0; i--)
  108.    { if ( !reached[V[i]] ) 
  109.       { S = DFS(G,V[i],reached);
  110.         forall(w,S) compnum[w] = count;
  111.         count++;
  112.        }
  113.     }
  115.  delete V;
  117.  return count;
  118.    
  119.  }