COIN-OR::LEMON - Graph Library

Changeset 1739:b1385f5da81b in lemon-0.x


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

Legend:

Unmodified
Added
Removed
  • lemon/topology.h

    r1709 r1739  
    3030///
    3131/// Topology related algorithms
     32///\todo Place the file contents is the module tree.
    3233
    3334namespace lemon {
     
    214215  }
    215216 
     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  }
    216267
    217268} //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.