# Changeset 1739:b1385f5da81b in lemon-0.x

Ignore:
Timestamp:
10/24/05 17:59:38 (15 years ago)
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:
1 edited

Unmodified
Added
Removed
• ## lemon/topology.h

 r1709 /// /// Topology related algorithms ///\todo Place the file contents is the module tree. namespace lemon { } ///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 int numberOfComponents(const UGraph &g) { int c=0; Bfs 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 int connectedComponents(const UGraph &g, WMap &comp) { int c=0; Bfs 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
Note: See TracChangeset for help on using the changeset viewer.