Changeset 1739:b1385f5da81b in lemon-0.x
- Timestamp:
- 10/24/05 17:59:38 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2267
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/topology.h
r1709 r1739 30 30 /// 31 31 /// Topology related algorithms 32 ///\todo Place the file contents is the module tree. 32 33 33 34 namespace lemon { … … 214 215 } 215 216 217 ///Count the number of connected components of an undirected graph 218 219 ///Count the number of connected components of an undirected graph 220 /// 221 ///\param g The graph. In must be undirected. 222 ///\return The number of components 223 ///\todo Test required 224 template<class UGraph> 225 int numberOfComponents(const UGraph &g) 226 { 227 int c=0; 228 Bfs<Graph> bfs(g); 229 bfs.init(); 230 for(typename Graph::NodeIt n(g);n!=INVALID;++n) 231 if(!bfs.reached(n)) { 232 c++; 233 bfs.addSource(n); 234 bfs.start(); 235 } 236 return c; 237 } 238 239 240 ///Find the connected components of an undirected graph 241 242 ///Find the connected components of an undirected graph 243 /// 244 ///\param g The graph. In must be undirected. 245 ///\retval comp A writable node map. The values will be set from 0 to 246 ///the number of the connected components minus one. Each values of the map 247 ///will be set exactly once, the values of a certain component will be 248 ///set continuously. 249 ///\return The number of components 250 ///\todo Test required 251 template<class UGraph, class WMap> 252 int connectedComponents(const UGraph &g, WMap &comp) 253 { 254 int c=0; 255 Bfs<Graph> bfs(g); 256 bfs.init(); 257 for(typename Graph::NodeIt n(g);n!=INVALID;++n) 258 if(!bfs.reached(n)) { 259 bfs.addSource(n); 260 while ( bfs.nextNode()!=INVALID ) { 261 comp[bfs.nextNode()]=c; 262 processNextNode(); 263 c++; 264 } 265 return c; 266 } 216 267 217 268 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.