Changeset 1739:b1385f5da81b in lemon-0.x for lemon/topology.h

Timestamp:

10/24/05 17:59:38 (18 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2267

Message:

Computing the number of the connected components and the components themselves.

File:

• lemon/topology.h (modified) (2 diffs)

lemon/topology.h

@@ -30 +30 @@
 ///
 /// Topology related algorithms
+///\todo Place the file contents is the module tree.
 
 namespace lemon {
@@ -214 +215 @@
   }
  
+  ///Count the number of connected components of an undirected graph
+
+  ///Count the number of connected components of an undirected graph
+  ///
+  ///\param g The graph. In must be undirected.
+  ///\return The number of components
+  ///\todo Test required
+  template<class UGraph>
+  int numberOfComponents(const UGraph &g)
+  {
+    int c=0;
+    Bfs<Graph> bfs(g);
+    bfs.init();
+    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
+      if(!bfs.reached(n)) {
+        c++;
+        bfs.addSource(n);
+        bfs.start();
+      }
+    return c;
+  }
+
+
+  ///Find the connected components of an undirected graph
+
+  ///Find the connected components of an undirected graph
+  ///
+  ///\param g The graph. In must be undirected.
+  ///\retval comp A writable node map. The values will be set from 0 to
+  ///the number of the connected components minus one. Each values of the map
+  ///will be set exactly once, the values of a certain component will be
+  ///set continuously.
+  ///\return The number of components
+  ///\todo Test required
+  template<class UGraph, class WMap>
+  int connectedComponents(const UGraph &g, WMap &comp)
+  {
+    int c=0;
+    Bfs<Graph> bfs(g);
+    bfs.init();
+    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
+      if(!bfs.reached(n)) {
+        bfs.addSource(n);
+        while ( bfs.nextNode()!=INVALID ) {
+          comp[bfs.nextNode()]=c;
+          processNextNode();
+          c++;
+      }
+    return c;
+  }
 
 } //namespace lemon