1.1 --- a/lemon/topology.h	Mon Oct 24 15:58:38 2005 +0000
     1.2 +++ b/lemon/topology.h	Mon Oct 24 15:59:38 2005 +0000
     1.3 @@ -29,6 +29,7 @@
     1.4  /// \brief Topology related algorithms
     1.5  ///
     1.6  /// Topology related algorithms
     1.7 +///\todo Place the file contents is the module tree.
     1.8  
     1.9  namespace lemon {
    1.10  
    1.11 @@ -213,6 +214,56 @@
    1.12      return true;
    1.13    }
    1.14   
    1.15 +  ///Count the number of connected components of an undirected graph
    1.16 +
    1.17 +  ///Count the number of connected components of an undirected graph
    1.18 +  ///
    1.19 +  ///\param g The graph. In must be undirected.
    1.20 +  ///\return The number of components
    1.21 +  ///\todo Test required
    1.22 +  template<class UGraph>
    1.23 +  int numberOfComponents(const UGraph &g)
    1.24 +  {
    1.25 +    int c=0;
    1.26 +    Bfs<Graph> bfs(g);
    1.27 +    bfs.init();
    1.28 +    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
    1.29 +      if(!bfs.reached(n)) {
    1.30 +	c++;
    1.31 +	bfs.addSource(n);
    1.32 +	bfs.start();
    1.33 +      }
    1.34 +    return c;
    1.35 +  }
    1.36 +
    1.37 +
    1.38 +  ///Find the connected components of an undirected graph
    1.39 +
    1.40 +  ///Find the connected components of an undirected graph
    1.41 +  ///
    1.42 +  ///\param g The graph. In must be undirected.
    1.43 +  ///\retval comp A writable node map. The values will be set from 0 to
    1.44 +  ///the number of the connected components minus one. Each values of the map
    1.45 +  ///will be set exactly once, the values of a certain component will be
    1.46 +  ///set continuously.
    1.47 +  ///\return The number of components
    1.48 +  ///\todo Test required
    1.49 +  template<class UGraph, class WMap>
    1.50 +  int connectedComponents(const UGraph &g, WMap &comp)
    1.51 +  {
    1.52 +    int c=0;
    1.53 +    Bfs<Graph> bfs(g);
    1.54 +    bfs.init();
    1.55 +    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
    1.56 +      if(!bfs.reached(n)) {
    1.57 +	bfs.addSource(n);
    1.58 +	while ( bfs.nextNode()!=INVALID ) {
    1.59 +	  comp[bfs.nextNode()]=c;
    1.60 +	  processNextNode();
    1.61 +	  c++;
    1.62 +      }
    1.63 +    return c;
    1.64 +  }
    1.65  
    1.66  } //namespace lemon
    1.67