COIN-OR::LEMON - Graph Library

Changeset 1740:4cade8579363 in lemon-0.x


Ignore:
Timestamp:
10/24/05 19:03:02 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2268
Message:

Bug fix in connectedComponents
Strongly connected components

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/topology.h

    r1739 r1740  
    1919
    2020#include <lemon/dfs.h>
     21#include <lemon/bfs.h>
    2122#include <lemon/graph_utils.h>
    2223
     
    221222  ///\param g The graph. In must be undirected.
    222223  ///\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);
     224  template <class UndirGraph>
     225  int countConnectedComponents(const UndirGraph &g) {
     226    checkConcept<concept::UndirGraph, UndirGraph>();
     227    int c = 0;
     228    Bfs<UndirGraph> bfs(g);
    229229    bfs.init();
    230     for(typename Graph::NodeIt n(g);n!=INVALID;++n)
     230    for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
    231231      if(!bfs.reached(n)) {
    232         c++;
    233232        bfs.addSource(n);
    234233        bfs.start();
    235       }
     234        ++c;
     235      }
     236    }
    236237    return c;
    237238  }
     
    249250  ///\return The number of components
    250251  ///\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);
     252  template <class UndirGraph, class IntNodeMap>
     253  int connectedComponents(const UndirGraph &g, IntNodeMap &comp) {
     254    checkConcept<concept::UndirGraph, UndirGraph>();
     255    checkConcept<concept::WriteMap<typename UndirGraph::Node, int>,
     256      IntNodeMap>();
     257    int c = 0;
     258    Bfs<UndirGraph> bfs(g);
    256259    bfs.init();
    257     for(typename Graph::NodeIt n(g);n!=INVALID;++n)
     260    for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
    258261      if(!bfs.reached(n)) {
    259262        bfs.addSource(n);
    260         while ( bfs.nextNode()!=INVALID ) {
    261           comp[bfs.nextNode()]=c;
    262           processNextNode();
    263           c++;
    264       }
     263        while (!bfs.emptyQueue()) {
     264          comp[bfs.nextNode()] = c;
     265          bfs.processNextNode();
     266        }
     267        ++c;
     268      }
     269    }
    265270    return c;
    266271  }
    267272
     273  namespace _components_bits {
     274
     275    template <typename Key, typename IntMap>
     276    struct FillWriteMap : public MapBase<Key, bool> {
     277    public:
     278      FillWriteMap(IntMap& _map, int& _comp)
     279        : map(_map), comp(_comp) {}
     280      void set(Key key, bool value) {
     281        if (value) { map.set(key, comp); }
     282      }
     283    private:
     284      IntMap& map;
     285      int& comp;
     286    };
     287
     288    template <typename Key, typename Container = std::vector<Key> >
     289    struct BackInserterWriteMap : public MapBase<Key, bool> {
     290    public:
     291      BackInserterWriteMap(Container& _container)
     292        : container(_container) {}
     293      void set(Key key, bool value) {
     294        if (value) { container.push_back(key); }
     295      }
     296    private:
     297      Container& container;
     298    };
     299
     300  }
     301
     302  /// \brief Count the strongly connected components of a directed graph
     303  ///
     304  /// Count the strongly connected components of a directed graph
     305  ///
     306  /// \param g The graph.
     307  /// \return The number of components
     308  template <typename Graph>
     309  int countStronglyConnectedComponents(const Graph& graph) {
     310    checkConcept<concept::StaticGraph, Graph>();
     311
     312    using namespace _components_bits;
     313
     314    typedef typename Graph::Node Node;
     315    typedef typename Graph::Edge Edge;
     316    typedef typename Graph::NodeIt NodeIt;
     317    typedef typename Graph::EdgeIt EdgeIt;
     318   
     319
     320    typename Dfs<Graph>::
     321      template DefProcessedMap<BackInserterWriteMap<Node> >::
     322      Create dfs(graph);
     323
     324    std::vector<Node> nodes;
     325    BackInserterWriteMap<Node> processed(nodes);
     326    dfs.processedMap(processed);
     327
     328    dfs.init();
     329    for (NodeIt it(graph); it != INVALID; ++it) {
     330      if (!dfs.reached(it)) {
     331        dfs.addSource(it);
     332        dfs.start();
     333      }
     334    }
     335
     336    typedef RevGraphAdaptor<const Graph> RGraph;
     337
     338    RGraph rgraph(graph);
     339
     340    Dfs<RGraph> rdfs(rgraph);
     341
     342    int num = 0;
     343
     344    rdfs.init();
     345    for (typename std::vector<Node>::reverse_iterator
     346           it = nodes.rbegin(); it != nodes.rend(); ++it) {
     347      if (!rdfs.reached(*it)) {
     348        rdfs.addSource(*it);
     349        rdfs.start();
     350        ++num;
     351      }
     352    }
     353    return num;
     354  }
     355
     356  /// \brief Find the strongly connected components of a directed graph
     357  ///
     358  /// Find the strongly connected components of a directed graph
     359  ///
     360  /// \param g The graph.
     361  /// \retval comp A writable node map. The values will be set from 0 to
     362  /// the number of the strongly connected components minus one. Each values
     363  /// of the map will be set exactly once, the values of a certain component
     364  /// will be set continuously.
     365  /// \return The number of components
     366  template <typename Graph, typename IntNodeMap>
     367  int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) {
     368    checkConcept<concept::StaticGraph, Graph>();
     369    checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>();
     370
     371    using namespace _components_bits;
     372
     373    typedef typename Graph::Node Node;
     374    typedef typename Graph::Edge Edge;
     375    typedef typename Graph::NodeIt NodeIt;
     376    typedef typename Graph::EdgeIt EdgeIt;
     377   
     378
     379    typename Dfs<Graph>::
     380      template DefProcessedMap<BackInserterWriteMap<Node> >::
     381      Create dfs(graph);
     382
     383    std::vector<Node> nodes;
     384    BackInserterWriteMap<Node> processed(nodes);
     385    dfs.processedMap(processed);
     386
     387    dfs.init();
     388    for (NodeIt it(graph); it != INVALID; ++it) {
     389      if (!dfs.reached(it)) {
     390        dfs.addSource(it);
     391        dfs.start();
     392      }
     393    }
     394
     395    typedef RevGraphAdaptor<const Graph> RGraph;
     396
     397    RGraph rgraph(graph);
     398
     399    typename Dfs<RGraph>::
     400      template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >::
     401      Create rdfs(rgraph);
     402
     403    int num = 0;
     404    FillWriteMap<Node, IntNodeMap> rprocessed(comp, num);
     405    rdfs.processedMap(rprocessed);
     406
     407    rdfs.init();
     408    for (typename std::vector<Node>::reverse_iterator
     409           it = nodes.rbegin(); it != nodes.rend(); ++it) {
     410      if (!rdfs.reached(*it)) {
     411        rdfs.addSource(*it);
     412        rdfs.start();
     413        ++num;
     414      }
     415    }
     416    return num;
     417  }
     418
    268419} //namespace lemon
    269420
Note: See TracChangeset for help on using the changeset viewer.