# HG changeset patch
# User alpar
# Date 1130169578 0
# Node ID b1385f5da81b81d8c775c70d1948d16d7105f549
# Parent  470aa67893f5fb311ff6fa5021dfc4d0c690d7ae
Computing the number of the connected components and the components themselves.

diff -r 470aa67893f5 -r b1385f5da81b lemon/topology.h
--- a/lemon/topology.h	Mon Oct 24 15:58:38 2005 +0000
+++ b/lemon/topology.h	Mon Oct 24 15:59:38 2005 +0000
@@ -29,6 +29,7 @@
 /// \brief Topology related algorithms
 ///
 /// Topology related algorithms
+///\todo Place the file contents is the module tree.
 
 namespace lemon {
 
@@ -213,6 +214,56 @@
     return true;
   }
  
+  ///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