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

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

数值算法/人工智能

开发平台：

MultiPlatform

_bicomponents.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _bicomponents.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. *  BICONNECTED COMPONENTS                                                      *
  17. *                                                                              *
  18. *  Michael Meiser (1991)                                                       *
  19. *                                                                              *
  20. *******************************************************************************/
  22. #include <LEDA/graph_alg.h>
  23. #include <LEDA/stack.h>
  27. static void bcc_dfs(const graph& G,node v,edge_array<int>& compnum,
  28.                     node_array<int>& dfsnum,node_array<int>& lowpt,
  29.                     node_array<node>& father,stack<node>& current,
  30.                     int& count1,int& count2);
  33. int BICONNECTED_COMPONENTS(const graph& G, edge_array<int>& compnum)
  34. {
  35.   // computes the biconnected components of the underlying  undirected
  36.   // graph,  returns m = number of biconnected components and 
  37.   // in edge_array<int> compnum for each edge an integer with
  38.   // compnum[x] = compnum[y] iff edges x and y belong to the same component 
  39.   // and 0 <= compnum[e] <= m-1 for all edges e
  40.   // running time : O(|V|+|E|)
  41.   //
  42.   // (problem  with self-loops ? )
  44.   stack<node> current;
  45.   node_array<int> dfsnum(G,-1);
  46.   node_array<int> lowpt(G,0);
  47.   node_array<node> father(G,nil);
  48.   int count1 = 0; 
  49.   int count2 = 0;
  50.   node v;
  52.   forall_nodes(v,G)
  53.    if (dfsnum[v] == -1)
  54.     {
  55.      dfsnum[v] = ++count1;
  56.      current.push(v);
  57.      bcc_dfs(G,v,compnum,dfsnum,lowpt,father,current,count1,count2);
  58.     }
  60.   return(count2);
  62.  } // BI_COMPONENTS
  66. static void bcc_dfs(const graph& G,node v,edge_array<int>& compnum,
  67.                     node_array<int>& dfsnum,node_array<int>& lowpt,
  68.                     node_array<node>& father,stack<node>& current,
  69.                     int& count1,int& count2)
  70.  {
  71.   // Precondition: G is undirected
  73.   node w;
  75.   lowpt[v] = dfsnum[v];
  77.   forall_adj_nodes(w,v)
  78.    if (dfsnum[w] == -1)
  79.     {
  80.      dfsnum[w] = ++count1;
  81.      current.push(w);
  82.      father[w] = v;
  83.      bcc_dfs(G,w,compnum,dfsnum,lowpt,father,current,count1,count2);
  84.      lowpt[v] = Min(lowpt[v],lowpt[w]);
  85.     }
  86.    else
  87.     lowpt[v] = Min(lowpt[v],dfsnum[w]);
  89.   if (father[v] && (lowpt[v] == dfsnum[father[v]]))
  90.    // 1.Bedingung nur von Bedeutung fuer Graphen,die nicht zusammen-
  91.    // haengend sind sowie fuer den ersten besuchten Knoten
  92.    {
  93.     edge e;
  95.     do
  96.      {
  97.       w = current.pop();
  98.       forall_adj_edges(e,w)
  99.        if (dfsnum[w] > dfsnum[G.opposite(w,e)])
  100.         compnum[e] = count2;
  101.      }
  102.     while (w != v);
  104.     count2++;
  105.    }
  107.  } // bcc_dfs