COIN-OR::LEMON - Graph Library

Changeset 1750:5c76ebbb4818 in lemon-0.x


Ignore:
Timestamp:
11/02/05 16:23:46 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2279
Message:

Connected components, etc...
Based on the dfs visitor interface

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r1639 r1750  
    126126
    127127/**
     128@defgroup topology Topology related algorithms
     129@ingroup galgs
     130\brief This group describes the algorithms
     131for discover the topology of the graphs.
     132*/
     133
     134/**
    128135@defgroup exceptions Exceptions
    129136This group contains the exceptions thrown by LEMON library
  • lemon/topology.h

    r1740 r1750  
    2121#include <lemon/bfs.h>
    2222#include <lemon/graph_utils.h>
     23#include <lemon/graph_adaptor.h>
     24#include <lemon/maps.h>
    2325
    2426#include <lemon/concept/graph.h>
     
    2628#include <lemon/concept_check.h>
    2729
    28 /// \ingroup flowalgs
     30#include <lemon/bin_heap.h>
     31#include <lemon/linear_heap.h>
     32
     33#include <stack>
     34#include <functional>
     35
     36/// \ingroup topology
    2937/// \file
    3038/// \brief Topology related algorithms
    3139///
    3240/// Topology related algorithms
    33 ///\todo Place the file contents is the module tree.
    3441
    3542namespace lemon {
    3643
     44  /// \ingroup topology
     45  ///
     46  /// \brief Check that the given undirected graph is connected.
     47  ///
     48  /// Check that the given undirected graph connected.
     49  /// \param graph The undirected graph.
     50  /// \return %True when there is path between any two nodes in the graph.
     51  /// \warning The empty graph is not connected.
     52  template <typename UndirGraph>
     53  bool connected(const UndirGraph& graph) {
     54    checkConcept<concept::UndirGraph, UndirGraph>();
     55    typedef typename UndirGraph::NodeIt NodeIt;
     56    if (NodeIt(graph) == INVALID) return false;
     57    Dfs<UndirGraph> dfs(graph);
     58    dfs.run(NodeIt(graph));
     59    for (NodeIt it(graph); it != INVALID; ++it) {
     60      if (!dfs.reached(it)) {
     61        return false;
     62      }
     63    }
     64    return true;
     65  }
     66
     67  /// \ingroup topology
     68  ///
     69  /// \brief Count the number of connected components of an undirected graph
     70  ///
     71  /// Count the number of connected components of an undirected graph
     72  ///
     73  /// \param g The graph. In must be undirected.
     74  /// \return The number of components
     75  template <typename UndirGraph>
     76  int countConnectedComponents(const UndirGraph &graph) {
     77    checkConcept<concept::UndirGraph, UndirGraph>();
     78    typedef typename UndirGraph::Node Node;
     79    typedef typename UndirGraph::Edge Edge;
     80
     81    typedef NullMap<Node, Edge> PredMap;
     82    typedef NullMap<Node, int> DistMap;
     83
     84    int compNum = 0;
     85    typename Bfs<UndirGraph>::
     86      template DefPredMap<PredMap>::
     87      template DefDistMap<DistMap>::
     88      Create bfs(graph);
     89
     90    PredMap predMap;
     91    bfs.predMap(predMap);
     92
     93    DistMap distMap;
     94    bfs.distMap(distMap);
     95
     96    bfs.init();
     97    for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
     98      if (!bfs.reached(n)) {
     99        bfs.addSource(n);
     100        bfs.start();
     101        ++compNum;
     102      }
     103    }
     104    return compNum;
     105  }
     106
     107  /// \ingroup topology
     108  ///
     109  /// \brief Find the connected components of an undirected graph
     110  ///
     111  /// Find the connected components of an undirected graph.
     112  ///
     113  /// \param g The graph. In must be undirected.
     114  /// \retval comp A writable node map. The values will be set from 0 to
     115  /// the number of the connected components minus one. Each values of the map
     116  /// will be set exactly once, the values of a certain component will be
     117  /// set continuously.
     118  /// \return The number of components
     119  template <class UndirGraph, class NodeMap>
     120  int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {
     121    checkConcept<concept::UndirGraph, UndirGraph>();
     122    typedef typename UndirGraph::Node Node;
     123    typedef typename UndirGraph::Edge Edge;
     124    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
     125
     126    typedef NullMap<Node, Edge> PredMap;
     127    typedef NullMap<Node, int> DistMap;
     128
     129    int compNum = 0;
     130    typename Bfs<UndirGraph>::
     131      template DefPredMap<PredMap>::
     132      template DefDistMap<DistMap>::
     133      Create bfs(graph);
     134
     135    PredMap predMap;
     136    bfs.predMap(predMap);
     137
     138    DistMap distMap;
     139    bfs.distMap(distMap);
     140   
     141    bfs.init();
     142    for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
     143      if(!bfs.reached(n)) {
     144        bfs.addSource(n);
     145        while (!bfs.emptyQueue()) {
     146          compMap.set(bfs.nextNode(), compNum);
     147          bfs.processNextNode();
     148        }
     149        ++compNum;
     150      }
     151    }
     152    return compNum;
     153  }
     154
    37155  namespace _topology_bits {
    38    
    39     template <typename NodeMap>
    40     class BackCounterMap {
     156
     157    template <typename Graph, typename Iterator >
     158    struct LeaveOrderVisitor : public DfsVisitor<Graph> {
    41159    public:
    42       BackCounterMap(NodeMap& _nodeMap, int _counter)
    43         : nodeMap(_nodeMap), counter(_counter) {}
    44 
    45       void set(typename NodeMap::Key key, bool val) {
    46         if (val) {
    47           nodeMap.set(key, --counter);
    48         } else {
    49           nodeMap.set(key, -1);
    50         }
    51       }
    52 
    53       bool operator[](typename NodeMap::Key key) const {
    54         return nodeMap[key] != -1;
     160      typedef typename Graph::Node Node;
     161      LeaveOrderVisitor(Iterator it) : _it(it) {}
     162
     163      void leave(const Node& node) {
     164        *(_it++) = node;
    55165      }
    56166
    57167    private:
    58       NodeMap& nodeMap;
    59       int counter;
     168      Iterator _it;
    60169    };
    61   }
    62 
    63   // \todo Its to special output // ReadWriteMap
     170
     171    template <typename Graph, typename Map>
     172    struct FillMapVisitor : public DfsVisitor<Graph> {
     173    public:
     174      typedef typename Graph::Node Node;
     175      typedef typename Map::Value Value;
     176
     177      FillMapVisitor(Map& map, Value& value)
     178        : _map(map), _value(value) {}
     179
     180      void reach(const Node& node) {
     181        _map.set(node, _value);
     182      }
     183    private:
     184      Map& _map;
     185      Value& _value;
     186    };
     187
     188    template <typename Graph, typename EdgeMap>
     189    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
     190    public:
     191      typedef typename Graph::Node Node;
     192      typedef typename Graph::Edge Edge;
     193
     194      StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap,
     195                                       int& cutNum)
     196        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
     197          _compMap(graph), _num(0) {
     198      }
     199
     200      void stop(const Node&) {
     201        ++_num;
     202      }
     203
     204      void reach(const Node& node) {
     205        _compMap.set(node, _num);
     206      }
     207
     208      void examine(const Edge& edge) {
     209        if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) {
     210          _cutMap.set(edge, true);
     211          ++_cutNum;
     212        }
     213      }
     214    private:
     215      const Graph& _graph;
     216      EdgeMap& _cutMap;
     217      int& _cutNum;
     218
     219      typename Graph::template NodeMap<int> _compMap;
     220      int _num;
     221    };
     222
     223  }
     224
     225
     226  /// \ingroup topology
     227  ///
     228  /// \brief Check that the given directed graph is strongly connected.
     229  ///
     230  /// Check that the given directed graph is strongly connected. The
     231  /// graph is strongly connected when any two nodes of the graph are
     232  /// connected with directed pathes in both direction.
     233  /// \return %False when the graph is not strongly connected.
     234  /// \see connected
     235  ///
     236  /// \waning Empty graph is not strongly connected.
     237  template <typename Graph>
     238  bool stronglyConnected(const Graph& graph) {
     239    checkConcept<concept::StaticGraph, Graph>();
     240    if (NodeIt(graph) == INVALID) return false;
     241
     242    typedef typename Graph::Node Node;
     243    typedef typename Graph::NodeIt NodeIt;
     244
     245    using namespace _topology_bits;
     246
     247    typedef DfsVisitor<Graph> Visitor;
     248    Visitor visitor;
     249
     250    DfsVisit<Graph, Visitor> dfs(graph, visitor);
     251    dfs.init();
     252    dfs.addSource(NodeIt(graph));
     253    dfs.start();
     254
     255    for (NodeIt it(graph); it != INVALID; ++it) {
     256      if (!dfs.reached(it)) {
     257        return false;
     258      }
     259    }
     260
     261    typedef RevGraphAdaptor<const Graph> RGraph;
     262    RGraph rgraph(graph);
     263
     264    typedef DfsVisitor<Graph> RVisitor;
     265    RVisitor rvisitor;
     266
     267    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
     268    rdfs.init();   
     269    rdfs.addSource(NodeIt(graph));
     270    rdfs.start();
     271
     272    for (NodeIt it(graph); it != INVALID; ++it) {
     273      if (!rdfs.reached(it)) {
     274        return false;
     275      }
     276    }
     277
     278    return true;
     279  }
     280
     281  /// \ingroup topology
     282  ///
     283  /// \brief Count the strongly connected components of a directed graph
     284  ///
     285  /// Count the strongly connected components of a directed graph.
     286  /// The strongly connected components are the classes of an equivalence
     287  /// relation on the nodes of the graph. Two nodes are connected with
     288  /// directed paths in both direction.
     289  ///
     290  /// \param g The graph.
     291  /// \return The number of components
     292  template <typename Graph>
     293  int countStronglyConnectedComponents(const Graph& graph) {
     294    checkConcept<concept::StaticGraph, Graph>();
     295
     296    using namespace _topology_bits;
     297
     298    typedef typename Graph::Node Node;
     299    typedef typename Graph::Edge Edge;
     300    typedef typename Graph::NodeIt NodeIt;
     301    typedef typename Graph::EdgeIt EdgeIt;
     302   
     303    typedef std::vector<Node> Container;
     304    typedef typename Container::iterator Iterator;
     305
     306    Container nodes(countNodes(graph));
     307    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
     308    Visitor visitor(nodes.begin());
     309     
     310    DfsVisit<Graph, Visitor> dfs(graph, visitor);
     311    dfs.init();
     312    for (NodeIt it(graph); it != INVALID; ++it) {
     313      if (!dfs.reached(it)) {
     314        dfs.addSource(it);
     315        dfs.start();
     316      }
     317    }
     318
     319    typedef typename Container::reverse_iterator RIterator;
     320    typedef RevGraphAdaptor<const Graph> RGraph;
     321
     322    RGraph rgraph(graph);
     323
     324    typedef DfsVisitor<Graph> RVisitor;
     325    RVisitor rvisitor;
     326
     327    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
     328
     329    int compNum = 0;
     330
     331    rdfs.init();
     332    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
     333      if (!rdfs.reached(*it)) {
     334        rdfs.addSource(*it);
     335        rdfs.start();
     336        ++compNum;
     337      }
     338    }
     339    return compNum;
     340  }
     341
     342  /// \ingroup topology
     343  ///
     344  /// \brief Find the strongly connected components of a directed graph
     345  ///
     346  /// Find the strongly connected components of a directed graph.
     347  /// The strongly connected components are the classes of an equivalence
     348  /// relation on the nodes of the graph. Two nodes are in relationship
     349  /// when there are directed paths between them in both direction.
     350  ///
     351  /// \param g The graph.
     352  /// \retval comp A writable node map. The values will be set from 0 to
     353  /// the number of the strongly connected components minus one. Each values
     354  /// of the map will be set exactly once, the values of a certain component
     355  /// will be set continuously.
     356  /// \return The number of components
    64357  template <typename Graph, typename NodeMap>
    65   bool topological_sort(const Graph& graph, NodeMap& nodeMap) {
     358  int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
     359    checkConcept<concept::StaticGraph, Graph>();
     360    typedef typename Graph::Node Node;
     361    typedef typename Graph::NodeIt NodeIt;
     362    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
     363
    66364    using namespace _topology_bits;
    67 
     365   
     366    typedef std::vector<Node> Container;
     367    typedef typename Container::iterator Iterator;
     368
     369    Container nodes(countNodes(graph));
     370    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
     371    Visitor visitor(nodes.begin());
     372     
     373    DfsVisit<Graph, Visitor> dfs(graph, visitor);
     374    dfs.init();
     375    for (NodeIt it(graph); it != INVALID; ++it) {
     376      if (!dfs.reached(it)) {
     377        dfs.addSource(it);
     378        dfs.start();
     379      }
     380    }
     381
     382    typedef typename Container::reverse_iterator RIterator;
     383    typedef RevGraphAdaptor<const Graph> RGraph;
     384
     385    RGraph rgraph(graph);
     386
     387    int compNum = 0;
     388
     389    typedef FillMapVisitor<RGraph, NodeMap> RVisitor;
     390    RVisitor rvisitor(compMap, compNum);
     391
     392    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
     393
     394    rdfs.init();
     395    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
     396      if (!rdfs.reached(*it)) {
     397        rdfs.addSource(*it);
     398        rdfs.start();
     399        ++compNum;
     400      }
     401    }
     402    return compNum;
     403  }
     404
     405  /// \ingroup topology
     406  ///
     407  /// \brief Find the cut edges of the strongly connected components.
     408  ///
     409  /// Find the cut edges of the strongly connected components.
     410  /// The strongly connected components are the classes of an equivalence
     411  /// relation on the nodes of the graph. Two nodes are in relationship
     412  /// when there are directed paths between them in both direction.
     413  /// The strongly connected components are separated by the cut edges.
     414  ///
     415  /// \param g The graph.
     416  /// \retval comp A writable edge map. The values will be set true when
     417  /// the edge is cut edge otherwise false.
     418  ///
     419  /// \return The number of cut edges
     420  template <typename Graph, typename EdgeMap>
     421  int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
    68422    checkConcept<concept::StaticGraph, Graph>();
    69     checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
     423    typedef typename Graph::Node Node;
     424    typedef typename Graph::Edge Edge;
     425    typedef typename Graph::NodeIt NodeIt;
     426    checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>();
     427
     428    using namespace _topology_bits;
     429   
     430    typedef std::vector<Node> Container;
     431    typedef typename Container::iterator Iterator;
     432
     433    Container nodes(countNodes(graph));
     434    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
     435    Visitor visitor(nodes.begin());
     436     
     437    DfsVisit<Graph, Visitor> dfs(graph, visitor);
     438    dfs.init();
     439    for (NodeIt it(graph); it != INVALID; ++it) {
     440      if (!dfs.reached(it)) {
     441        dfs.addSource(it);
     442        dfs.start();
     443      }
     444    }
     445
     446    typedef typename Container::reverse_iterator RIterator;
     447    typedef RevGraphAdaptor<const Graph> RGraph;
     448
     449    RGraph rgraph(graph);
     450
     451    int cutNum = 0;
     452
     453    typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;
     454    RVisitor rvisitor(rgraph, cutMap, cutNum);
     455
     456    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
     457
     458    rdfs.init();
     459    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
     460      if (!rdfs.reached(*it)) {
     461        rdfs.addSource(*it);
     462        rdfs.start();
     463      }
     464    }
     465    return cutNum;
     466  }
     467
     468  namespace _topology_bits {
     469   
     470    template <typename Graph>
     471    class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
     472    public:
     473      typedef typename Graph::Node Node;
     474      typedef typename Graph::Edge Edge;
     475      typedef typename Graph::UndirEdge UndirEdge;
     476
     477      CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum)
     478        : _graph(graph), _compNum(compNum),
     479          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
     480
     481      void start(const Node& node) {
     482        _predMap.set(node, INVALID);
     483      }
     484     
     485      void reach(const Node& node) {
     486        _numMap.set(node, _num);
     487        _retMap.set(node, _num);
     488        ++_num;
     489      }
     490
     491      void discover(const Edge& edge) {
     492        _predMap.set(_graph.target(edge), _graph.source(edge));
     493      }
     494
     495      void examine(const Edge& edge) {
     496        if (_graph.source(edge) == _graph.target(edge) &&
     497            _graph.direction(edge)) {
     498          ++_compNum;
     499          return;
     500        }
     501        if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
     502          return;
     503        }
     504        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
     505          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
     506        }
     507      }
     508
     509      void backtrack(const Edge& edge) {
     510        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
     511          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
     512        } 
     513        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
     514          ++_compNum;
     515        }
     516      }
     517     
     518    private:
     519      const Graph& _graph;
     520      int& _compNum;
     521
     522      typename Graph::template NodeMap<int> _numMap;
     523      typename Graph::template NodeMap<int> _retMap;
     524      typename Graph::template NodeMap<Node> _predMap;
     525      int _num;
     526    };
     527
     528    template <typename Graph, typename EdgeMap>
     529    class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
     530    public:
     531      typedef typename Graph::Node Node;
     532      typedef typename Graph::Edge Edge;
     533      typedef typename Graph::UndirEdge UndirEdge;
     534
     535      NodeBiconnectedComponentsVisitor(const Graph& graph,
     536                                       EdgeMap& compMap, int &compNum)
     537        : _graph(graph), _compMap(compMap), _compNum(compNum),
     538          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
     539
     540      void start(const Node& node) {
     541        _predMap.set(node, INVALID);
     542      }
     543     
     544      void reach(const Node& node) {
     545        _numMap.set(node, _num);
     546        _retMap.set(node, _num);
     547        ++_num;
     548      }
     549
     550      void discover(const Edge& edge) {
     551        Node target = _graph.target(edge);
     552        _predMap.set(target, edge);
     553        _edgeStack.push(edge);
     554      }
     555
     556      void examine(const Edge& edge) {
     557        Node source = _graph.source(edge);
     558        Node target = _graph.target(edge);
     559        if (source == target && _graph.direction(edge)) {
     560          _compMap.set(edge, _compNum);
     561          ++_compNum;
     562          return;
     563        }
     564        if (_numMap[target] < _numMap[source]) {
     565          if (_predMap[source] != _graph.oppositeEdge(edge)) {
     566            _edgeStack.push(edge);
     567          }
     568        }
     569        if (_predMap[source] != INVALID &&
     570            target == _graph.source(_predMap[source])) {
     571          return;
     572        }
     573        if (_retMap[source] > _numMap[target]) {
     574          _retMap.set(source, _numMap[target]);
     575        }
     576      }
     577
     578      void backtrack(const Edge& edge) {
     579        Node source = _graph.source(edge);
     580        Node target = _graph.target(edge);
     581        if (_retMap[source] > _retMap[target]) {
     582          _retMap.set(source, _retMap[target]);
     583        } 
     584        if (_numMap[source] <= _retMap[target]) {
     585          while (_edgeStack.top() != edge) {
     586            _compMap.set(_edgeStack.top(), _compNum);
     587            _edgeStack.pop();
     588          }
     589          _compMap.set(edge, _compNum);
     590          _edgeStack.pop();
     591          ++_compNum;
     592        }
     593      }
     594     
     595    private:
     596      const Graph& _graph;
     597      EdgeMap& _compMap;
     598      int& _compNum;
     599
     600      typename Graph::template NodeMap<int> _numMap;
     601      typename Graph::template NodeMap<int> _retMap;
     602      typename Graph::template NodeMap<Edge> _predMap;
     603      std::stack<UndirEdge> _edgeStack;
     604      int _num;
     605    };
     606
     607
     608    template <typename Graph, typename NodeMap>
     609    class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {
     610    public:
     611      typedef typename Graph::Node Node;
     612      typedef typename Graph::Edge Edge;
     613      typedef typename Graph::UndirEdge UndirEdge;
     614
     615      NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
     616                                     int& cutNum)
     617        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
     618          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
     619
     620      void start(const Node& node) {
     621        _predMap.set(node, INVALID);
     622        rootCut = false;
     623      }
     624     
     625      void reach(const Node& node) {
     626        _numMap.set(node, _num);
     627        _retMap.set(node, _num);
     628        ++_num;
     629      }
     630
     631      void discover(const Edge& edge) {
     632        _predMap.set(_graph.target(edge), _graph.source(edge));
     633      }
     634
     635      void examine(const Edge& edge) {
     636        if (_graph.source(edge) == _graph.target(edge) &&
     637            _graph.direction(edge)) {
     638          if (!_cutMap[_graph.source(edge)]) {
     639            _cutMap.set(_graph.source(edge), true);
     640            ++_cutNum;
     641          }
     642          return;
     643        }
     644        if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
     645        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
     646          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
     647        }
     648      }
     649
     650      void backtrack(const Edge& edge) {
     651        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
     652          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
     653        } 
     654        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
     655          if (_predMap[_graph.source(edge)] != INVALID) {
     656            if (!_cutMap[_graph.source(edge)]) {
     657              _cutMap.set(_graph.source(edge), true);
     658              ++_cutNum;
     659            }
     660          } else if (rootCut) {
     661            if (!_cutMap[_graph.source(edge)]) {
     662              _cutMap.set(_graph.source(edge), true);
     663              ++_cutNum;
     664            }
     665          } else {
     666            rootCut = true;
     667          }
     668        }
     669      }
     670     
     671    private:
     672      const Graph& _graph;
     673      NodeMap& _cutMap;
     674      int& _cutNum;
     675
     676      typename Graph::template NodeMap<int> _numMap;
     677      typename Graph::template NodeMap<int> _retMap;
     678      typename Graph::template NodeMap<Node> _predMap;
     679      std::stack<UndirEdge> _edgeStack;
     680      int _num;
     681      bool rootCut;
     682    };
     683
     684  }
     685
     686  template <typename UndirGraph>
     687  int countNodeBiconnectedComponents(const UndirGraph& graph);
     688
     689  /// \ingroup topology
     690  ///
     691  /// \brief Checks the graph is node biconnected.
     692  ///
     693  /// This function checks that the undirected graph is node biconnected 
     694  /// graph. The graph is node biconnected if any two undirected edge is
     695  /// on same circle.
     696  ///
     697  /// \param graph The graph.
     698  /// \return %True when the graph node biconnected.
     699  /// \todo Make it faster.
     700  template <typename UndirGraph>
     701  bool nodeBiconnected(const UndirGraph& graph) {
     702    return countNodeBiconnectedComponents(graph) == 1;
     703  }
     704
     705  /// \ingroup topology
     706  ///
     707  /// \brief Count the biconnected components.
     708  ///
     709  /// This function finds the node biconnected components in an undirected
     710  /// graph. The biconnected components are the classes of an equivalence
     711  /// relation on the undirected edges. Two undirected edge is in relationship
     712  /// when they are on same circle.
     713  ///
     714  /// \param graph The graph.
     715  /// \return The number of components.
     716  template <typename UndirGraph>
     717  int countNodeBiconnectedComponents(const UndirGraph& graph) {
     718    checkConcept<concept::UndirGraph, UndirGraph>();
     719    typedef typename UndirGraph::NodeIt NodeIt;
     720
     721    using namespace _topology_bits;
     722
     723    typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;
     724
     725    int compNum = 0;
     726    Visitor visitor(graph, compNum);
     727
     728    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     729    dfs.init();
     730   
     731    for (NodeIt it(graph); it != INVALID; ++it) {
     732      if (!dfs.reached(it)) {
     733        dfs.addSource(it);
     734        dfs.start();
     735      }
     736    }
     737    return compNum;
     738  }
     739
     740  /// \ingroup topology
     741  ///
     742  /// \brief Find the node biconnected components.
     743  ///
     744  /// This function finds the node biconnected components in an undirected
     745  /// graph. The node biconnected components are the classes of an equivalence
     746  /// relation on the undirected edges. Two undirected edge are in relationship
     747  /// when they are on same circle.
     748  ///
     749  /// \param graph The graph.
     750  /// \retval comp A writable undir edge map. The values will be set from 0 to
     751  /// the number of the biconnected components minus one. Each values
     752  /// of the map will be set exactly once, the values of a certain component
     753  /// will be set continuously.
     754  /// \return The number of components.
     755  template <typename UndirGraph, typename UndirEdgeMap>
     756  int nodeBiconnectedComponents(const UndirGraph& graph,
     757                                UndirEdgeMap& compMap) {
     758    checkConcept<concept::UndirGraph, UndirGraph>();
     759    typedef typename UndirGraph::NodeIt NodeIt;
     760    typedef typename UndirGraph::UndirEdge UndirEdge;
     761    checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>();
     762
     763    using namespace _topology_bits;
     764
     765    typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
     766   
     767    int compNum = 0;
     768    Visitor visitor(graph, compMap, compNum);
     769
     770    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     771    dfs.init();
     772   
     773    for (NodeIt it(graph); it != INVALID; ++it) {
     774      if (!dfs.reached(it)) {
     775        dfs.addSource(it);
     776        dfs.start();
     777      }
     778    }
     779    return compNum;
     780  }
     781
     782  /// \ingroup topology
     783  ///
     784  /// \brief Find the node biconnected cut nodes.
     785  ///
     786  /// This function finds the node biconnected cut nodes in an undirected
     787  /// graph. The node biconnected components are the classes of an equivalence
     788  /// relation on the undirected edges. Two undirected edges are in
     789  /// relationship when they are on same circle. The biconnected components
     790  /// are separted by nodes which are the cut nodes of the components.
     791  ///
     792  /// \param graph The graph.
     793  /// \retval comp A writable edge map. The values will be set true when
     794  /// the node separate two or more components.
     795  /// \return The number of the cut nodes.
     796  template <typename UndirGraph, typename NodeMap>
     797  int nodeBiconnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {
     798    checkConcept<concept::UndirGraph, UndirGraph>();
     799    typedef typename UndirGraph::Node Node;
     800    typedef typename UndirGraph::NodeIt NodeIt;
     801    checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
     802
     803    using namespace _topology_bits;
     804
     805    typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
     806   
     807    int cutNum = 0;
     808    Visitor visitor(graph, cutMap, cutNum);
     809
     810    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     811    dfs.init();
     812   
     813    for (NodeIt it(graph); it != INVALID; ++it) {
     814      if (!dfs.reached(it)) {
     815        dfs.addSource(it);
     816        dfs.start();
     817      }
     818    }
     819    return cutNum;
     820  }
     821
     822  namespace _topology_bits {
     823   
     824    template <typename Graph>
     825    class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
     826    public:
     827      typedef typename Graph::Node Node;
     828      typedef typename Graph::Edge Edge;
     829      typedef typename Graph::UndirEdge UndirEdge;
     830
     831      CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum)
     832        : _graph(graph), _compNum(compNum),
     833          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
     834
     835      void start(const Node& node) {
     836        _predMap.set(node, INVALID);
     837      }
     838     
     839      void reach(const Node& node) {
     840        _numMap.set(node, _num);
     841        _retMap.set(node, _num);
     842        ++_num;
     843      }
     844     
     845      void leave(const Node& node) {
     846        if (_numMap[node] <= _retMap[node]) {
     847          ++_compNum;
     848        }       
     849      }
     850
     851      void discover(const Edge& edge) {
     852        _predMap.set(_graph.target(edge), edge);
     853      }
     854
     855      void examine(const Edge& edge) {
     856        if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
     857          return;
     858        }
     859        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
     860          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
     861        }
     862      }
     863
     864      void backtrack(const Edge& edge) {
     865        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
     866          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
     867        } 
     868      }
     869     
     870    private:
     871      const Graph& _graph;
     872      int& _compNum;
     873
     874      typename Graph::template NodeMap<int> _numMap;
     875      typename Graph::template NodeMap<int> _retMap;
     876      typename Graph::template NodeMap<Edge> _predMap;
     877      int _num;
     878    };
     879
     880    template <typename Graph, typename NodeMap>
     881    class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
     882    public:
     883      typedef typename Graph::Node Node;
     884      typedef typename Graph::Edge Edge;
     885      typedef typename Graph::UndirEdge UndirEdge;
     886
     887      EdgeBiconnectedComponentsVisitor(const Graph& graph,
     888                                       NodeMap& compMap, int &compNum)
     889        : _graph(graph), _compMap(compMap), _compNum(compNum),
     890          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
     891
     892      void start(const Node& node) {
     893        _predMap.set(node, INVALID);
     894      }
     895     
     896      void reach(const Node& node) {
     897        _numMap.set(node, _num);
     898        _retMap.set(node, _num);
     899        _nodeStack.push(node);
     900        ++_num;
     901      }
     902     
     903      void leave(const Node& node) {
     904        if (_numMap[node] <= _retMap[node]) {
     905          while (_nodeStack.top() != node) {
     906            _compMap.set(_nodeStack.top(), _compNum);
     907            _nodeStack.pop();
     908          }
     909          _compMap.set(node, _compNum);
     910          _nodeStack.pop();
     911          ++_compNum;
     912        }       
     913      }
     914
     915      void discover(const Edge& edge) {
     916        _predMap.set(_graph.target(edge), edge);
     917      }
     918
     919      void examine(const Edge& edge) {
     920        if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
     921          return;
     922        }
     923        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
     924          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
     925        }
     926      }
     927
     928      void backtrack(const Edge& edge) {
     929        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
     930          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
     931        } 
     932      }
     933     
     934    private:
     935      const Graph& _graph;
     936      NodeMap& _compMap;
     937      int& _compNum;
     938
     939      typename Graph::template NodeMap<int> _numMap;
     940      typename Graph::template NodeMap<int> _retMap;
     941      typename Graph::template NodeMap<Edge> _predMap;
     942      std::stack<Node> _nodeStack;
     943      int _num;
     944    };
     945
     946
     947    template <typename Graph, typename EdgeMap>
     948    class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {
     949    public:
     950      typedef typename Graph::Node Node;
     951      typedef typename Graph::Edge Edge;
     952      typedef typename Graph::UndirEdge UndirEdge;
     953
     954      EdgeBiconnectedCutEdgesVisitor(const Graph& graph,
     955                                     EdgeMap& cutMap, int &cutNum)
     956        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
     957          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
     958
     959      void start(const Node& node) {
     960        _predMap[node] = INVALID;
     961      }
     962     
     963      void reach(const Node& node) {
     964        _numMap.set(node, _num);
     965        _retMap.set(node, _num);
     966        ++_num;
     967      }
     968     
     969      void leave(const Node& node) {
     970        if (_numMap[node] <= _retMap[node]) {
     971          if (_predMap[node] != INVALID) {
     972            _cutMap.set(_predMap[node], true);
     973            ++_cutNum;
     974          }
     975        }       
     976      }
     977
     978      void discover(const Edge& edge) {
     979        _predMap.set(_graph.target(edge), edge);
     980      }
     981
     982      void examine(const Edge& edge) {
     983        if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
     984          return;
     985        }
     986        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
     987          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
     988        }
     989      }
     990
     991      void backtrack(const Edge& edge) {
     992        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
     993          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
     994        } 
     995      }
     996     
     997    private:
     998      const Graph& _graph;
     999      EdgeMap& _cutMap;
     1000      int& _cutNum;
     1001
     1002      typename Graph::template NodeMap<int> _numMap;
     1003      typename Graph::template NodeMap<int> _retMap;
     1004      typename Graph::template NodeMap<Edge> _predMap;
     1005      int _num;
     1006    };
     1007  }
     1008
     1009  template <typename UndirGraph>
     1010  int countEdgeBiconnectedComponents(const UndirGraph& graph);
     1011
     1012  /// \ingroup topology
     1013  ///
     1014  /// \brief Checks that the graph is edge biconnected.
     1015  ///
     1016  /// This function checks that the graph is edge biconnected. The undirected
     1017  /// graph is edge biconnected when any two nodes are connected with two
     1018  /// edge-disjoint paths.
     1019  ///
     1020  /// \param graph The undirected graph.
     1021  /// \return The number of components.
     1022  /// \todo Make it faster.
     1023  template <typename UndirGraph>
     1024  bool edgeBiconnected(const UndirGraph& graph) {
     1025    return countEdgeBiconnectedComponents(graph) == 1;
     1026  }
     1027
     1028  /// \ingroup topology
     1029  ///
     1030  /// \brief Count the edge biconnected components.
     1031  ///
     1032  /// This function count the edge biconnected components in an undirected
     1033  /// graph. The edge biconnected components are the classes of an equivalence
     1034  /// relation on the nodes. Two nodes are in relationship when they are 
     1035  /// connected with at least two edge-disjoint paths.
     1036  ///
     1037  /// \param graph The undirected graph.
     1038  /// \return The number of components.
     1039  template <typename UndirGraph>
     1040  int countEdgeBiconnectedComponents(const UndirGraph& graph) {
     1041    checkConcept<concept::UndirGraph, UndirGraph>();
     1042    typedef typename UndirGraph::NodeIt NodeIt;
     1043
     1044    using namespace _topology_bits;
     1045
     1046    typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;
     1047   
     1048    int compNum = 0;
     1049    Visitor visitor(graph, compNum);
     1050
     1051    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     1052    dfs.init();
     1053   
     1054    for (NodeIt it(graph); it != INVALID; ++it) {
     1055      if (!dfs.reached(it)) {
     1056        dfs.addSource(it);
     1057        dfs.start();
     1058      }
     1059    }
     1060    return compNum;
     1061  }
     1062
     1063  /// \ingroup topology
     1064  ///
     1065  /// \brief Find the edge biconnected components.
     1066  ///
     1067  /// This function finds the edge biconnected components in an undirected
     1068  /// graph. The edge biconnected components are the classes of an equivalence
     1069  /// relation on the nodes. Two nodes are in relationship when they are 
     1070  /// connected at least two edge-disjoint paths.
     1071  ///
     1072  /// \param graph The graph.
     1073  /// \retval comp A writable node map. The values will be set from 0 to
     1074  /// the number of the biconnected components minus one. Each values
     1075  /// of the map will be set exactly once, the values of a certain component
     1076  /// will be set continuously.
     1077  /// \return The number of components.
     1078  template <typename UndirGraph, typename NodeMap>
     1079  int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) {
     1080    checkConcept<concept::UndirGraph, UndirGraph>();
     1081    typedef typename UndirGraph::NodeIt NodeIt;
     1082    typedef typename UndirGraph::Node Node;
     1083    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
     1084
     1085    using namespace _topology_bits;
     1086
     1087    typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
     1088   
     1089    int compNum = 0;
     1090    Visitor visitor(graph, compMap, compNum);
     1091
     1092    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     1093    dfs.init();
     1094   
     1095    for (NodeIt it(graph); it != INVALID; ++it) {
     1096      if (!dfs.reached(it)) {
     1097        dfs.addSource(it);
     1098        dfs.start();
     1099      }
     1100    }
     1101    return compNum;
     1102  }
     1103
     1104  /// \ingroup topology
     1105  ///
     1106  /// \brief Find the edge biconnected cut edges.
     1107  ///
     1108  /// This function finds the edge biconnected components in an undirected
     1109  /// graph. The edge biconnected components are the classes of an equivalence
     1110  /// relation on the nodes. Two nodes are in relationship when they are
     1111  /// connected with at least two edge-disjoint paths. The edge biconnected
     1112  /// components are separted by edges which are the cut edges of the
     1113  /// components.
     1114  ///
     1115  /// \param graph The graph.
     1116  /// \retval comp A writable node map. The values will be set true when the
     1117  /// edge is a cut edge.
     1118  /// \return The number of cut edges.
     1119  template <typename UndirGraph, typename UndirEdgeMap>
     1120  int edgeBiconnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) {
     1121    checkConcept<concept::UndirGraph, UndirGraph>();
     1122    typedef typename UndirGraph::NodeIt NodeIt;
     1123    typedef typename UndirGraph::UndirEdge UndirEdge;
     1124    checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>();
     1125
     1126    using namespace _topology_bits;
     1127
     1128    typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
     1129   
     1130    int cutNum = 0;
     1131    Visitor visitor(graph, cutMap, cutNum);
     1132
     1133    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     1134    dfs.init();
     1135   
     1136    for (NodeIt it(graph); it != INVALID; ++it) {
     1137      if (!dfs.reached(it)) {
     1138        dfs.addSource(it);
     1139        dfs.start();
     1140      }
     1141    }
     1142    return cutNum;
     1143  }
     1144
     1145
     1146  namespace _topology_bits {
     1147   
     1148    template <typename Graph, typename IntNodeMap>
     1149    class TopologicalSortVisitor : public DfsVisitor<Graph> {
     1150    public:
     1151      typedef typename Graph::Node Node;
     1152      typedef typename Graph::Edge edge;
     1153
     1154      TopologicalSortVisitor(IntNodeMap& order, int num)
     1155        : _order(order), _num(num) {}
     1156     
     1157      void leave(const Node& node) {
     1158        _order.set(node, --_num);
     1159      }
     1160
     1161    private:
     1162      IntNodeMap& _order;
     1163      int _num;
     1164    };
     1165   
     1166  }
     1167
     1168  /// \ingroup topology
     1169  ///
     1170  /// \brief Sort the nodes of a DAG into topolgical order.
     1171  ///
     1172  /// Sort the nodes of a DAG into topolgical order.
     1173  ///
     1174  /// \param g The graph. In must be directed and acyclic.
     1175  /// \retval comp A writable node map. The values will be set from 0 to
     1176  /// the number of the nodes in the graph minus one. Each values of the map
     1177  /// will be set exactly once, the values  will be set descending order.
     1178  ///
     1179  /// \see checkedTopologicalSort
     1180  /// \see dag
     1181  template <typename Graph, typename NodeMap>
     1182  void topologicalSort(const Graph& graph, NodeMap& order) {
     1183    using namespace _topology_bits;
     1184
     1185    checkConcept<concept::StaticGraph, Graph>();
     1186    checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
    701187
    711188    typedef typename Graph::Node Node;
     
    731190    typedef typename Graph::Edge Edge;
    741191
    75     typedef BackCounterMap<NodeMap> ProcessedMap;
     1192    TopologicalSortVisitor<Graph, NodeMap>
     1193      visitor(order, countNodes(graph));
     1194
     1195    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
     1196      dfs(graph, visitor);
     1197
     1198    dfs.init();
     1199    for (NodeIt it(graph); it != INVALID; ++it) {
     1200      if (!dfs.reached(it)) {
     1201        dfs.addSource(it);
     1202        dfs.start();
     1203      }
     1204    }   
     1205  }
     1206
     1207  /// \ingroup topology
     1208  ///
     1209  /// \brief Sort the nodes of a DAG into topolgical order.
     1210  ///
     1211  /// Sort the nodes of a DAG into topolgical order. It also checks
     1212  /// that the given graph is DAG.
     1213  ///
     1214  /// \param g The graph. In must be directed and acyclic.
     1215  /// \retval order A readable - writable node map. The values will be set
     1216  /// from 0 to the number of the nodes in the graph minus one. Each values
     1217  /// of the map will be set exactly once, the values will be set descending
     1218  /// order.
     1219  /// \return %False when the graph is not DAG.
     1220  ///
     1221  /// \see topologicalSort
     1222  /// \see dag
     1223  template <typename Graph, typename NodeMap>
     1224  bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
     1225    using namespace _topology_bits;
     1226
     1227    checkConcept<concept::StaticGraph, Graph>();
     1228    checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
     1229
     1230    typedef typename Graph::Node Node;
     1231    typedef typename Graph::NodeIt NodeIt;
     1232    typedef typename Graph::Edge Edge;
     1233
     1234    order = constMap<Node, int, -1>();
     1235
     1236    TopologicalSortVisitor<Graph, NodeMap>
     1237      visitor(order, countNodes(graph));
     1238
     1239    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
     1240      dfs(graph, visitor);
     1241
     1242    dfs.init();
     1243    for (NodeIt it(graph); it != INVALID; ++it) {
     1244      if (!dfs.reached(it)) {
     1245        dfs.addSource(it);
     1246        while (!dfs.emptyQueue()) {
     1247          Edge edge = dfs.nextEdge();
     1248          Node target = graph.target(edge);
     1249          if (dfs.reached(target) && order[target] == -1) {
     1250            return false;
     1251          }
     1252          dfs.processNextEdge();
     1253        }
     1254      }
     1255    }
     1256    return true;
     1257  }
     1258
     1259  /// \ingroup topology
     1260  ///
     1261  /// \brief Check that the given directed graph is a DAG.
     1262  ///
     1263  /// Check that the given directed graph is a DAG. The DAG is
     1264  /// an Directed Acyclic Graph.
     1265  /// \return %False when the graph is not DAG.
     1266  /// \see acyclic
     1267  template <typename Graph>
     1268  bool dag(const Graph& graph) {
     1269
     1270    checkConcept<concept::StaticGraph, Graph>();
     1271
     1272    typedef typename Graph::Node Node;
     1273    typedef typename Graph::NodeIt NodeIt;
     1274    typedef typename Graph::Edge Edge;
     1275
     1276    typedef typename Graph::template NodeMap<bool> ProcessedMap;
    761277
    771278    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
    781279      Create dfs(graph);
    791280
    80     ProcessedMap processed(nodeMap, countNodes(graph));
    81 
     1281    ProcessedMap processed(graph);
    821282    dfs.processedMap(processed);
     1283
    831284    dfs.init();
    841285    for (NodeIt it(graph); it != INVALID; ++it) {
     
    981299  }
    991300
    100   /// \brief Check that the given graph is a DAG.
    101   ///
    102   /// Check that the given graph is a DAG. The DAG is
    103   /// an Directed Acyclic Graph.
    104   template <typename Graph>
    105   bool dag(const Graph& graph) {
    106 
    107     checkConcept<concept::StaticGraph, Graph>();
    108 
    109     typedef typename Graph::Node Node;
    110     typedef typename Graph::NodeIt NodeIt;
    111     typedef typename Graph::Edge Edge;
    112 
    113     typedef typename Graph::template NodeMap<bool> ProcessedMap;
    114 
    115     typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
    116       Create dfs(graph);
    117 
    118     ProcessedMap processed(graph);
    119     dfs.processedMap(processed);
    120 
    121     dfs.init();
    122     for (NodeIt it(graph); it != INVALID; ++it) {
    123       if (!dfs.reached(it)) {
    124         dfs.addSource(it);
    125         while (!dfs.emptyQueue()) {
    126           Edge edge = dfs.nextEdge();
    127           Node target = graph.target(edge);
    128           if (dfs.reached(target) && !processed[target]) {
    129             return false;
    130           }
    131           dfs.processNextEdge();
    132         }
    133       }
    134     }   
    135     return true;
    136   }
    137 
    138   // UndirGraph algorithms
    139 
    140   /// \brief Check that the given undirected graph is connected.
    141   ///
    142   /// Check that the given undirected graph connected.
    143   template <typename UndirGraph>
    144   bool connected(const UndirGraph& graph) {
    145     checkConcept<concept::UndirGraph, UndirGraph>();
    146     typedef typename UndirGraph::NodeIt NodeIt;
    147     if (NodeIt(graph) == INVALID) return false;
    148     Dfs<UndirGraph> dfs(graph);
    149     dfs.run(NodeIt(graph));
    150     for (NodeIt it(graph); it != INVALID; ++it) {
    151       if (!dfs.reached(it)) {
    152         return false;
    153       }
    154     }
    155     return true;
    156   }
    157 
     1301  /// \ingroup topology
     1302  ///
    1581303  /// \brief Check that the given undirected graph is acyclic.
    1591304  ///
    1601305  /// Check that the given undirected graph acyclic.
     1306  /// \param graph The undirected graph.
     1307  /// \return %True when there is no circle in the graph.
     1308  /// \see dag
    1611309  template <typename UndirGraph>
    1621310  bool acyclic(const UndirGraph& graph) {
     
    1851333  }
    1861334
     1335  /// \ingroup topology
     1336  ///
    1871337  /// \brief Check that the given undirected graph is tree.
    1881338  ///
    1891339  /// Check that the given undirected graph is tree.
     1340  /// \param graph The undirected graph.
     1341  /// \return %True when the graph is acyclic and connected.
    1901342  template <typename UndirGraph>
    1911343  bool tree(const UndirGraph& graph) {
     
    1941346    typedef typename UndirGraph::NodeIt NodeIt;
    1951347    typedef typename UndirGraph::Edge Edge;
    196     if (NodeIt(graph) == INVALID) return false;
    1971348    Dfs<UndirGraph> dfs(graph);
    1981349    dfs.init();
     
    2151366    return true;
    2161367  }
    217  
    218   ///Count the number of connected components of an undirected graph
    219 
    220   ///Count the number of connected components of an undirected graph
    221   ///
    222   ///\param g The graph. In must be undirected.
    223   ///\return The number of components
    224   template <class UndirGraph>
    225   int countConnectedComponents(const UndirGraph &g) {
     1368
     1369  /// \ingroup topology
     1370  ///
     1371  /// \brief Check that the given undirected graph is bipartite.
     1372  ///
     1373  /// Check that the given undirected graph is bipartite.
     1374  /// \param graph The undirected graph.
     1375  /// \return %True when the nodes can be separated into two sets that
     1376  /// there are not connected nodes in neither sets.
     1377  template <typename UndirGraph>
     1378  bool bipartite(const UndirGraph& graph) {
    2261379    checkConcept<concept::UndirGraph, UndirGraph>();
    227     int c = 0;
    228     Bfs<UndirGraph> bfs(g);
    229     bfs.init();
    230     for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
    231       if(!bfs.reached(n)) {
    232         bfs.addSource(n);
    233         bfs.start();
    234         ++c;
    235       }
    236     }
    237     return c;
    238   }
    239 
    240 
    241   ///Find the connected components of an undirected graph
    242 
    243   ///Find the connected components of an undirected graph
    244   ///
    245   ///\param g The graph. In must be undirected.
    246   ///\retval comp A writable node map. The values will be set from 0 to
    247   ///the number of the connected components minus one. Each values of the map
    248   ///will be set exactly once, the values of a certain component will be
    249   ///set continuously.
    250   ///\return The number of components
    251   ///\todo Test required
    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);
    259     bfs.init();
    260     for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
    261       if(!bfs.reached(n)) {
    262         bfs.addSource(n);
    263         while (!bfs.emptyQueue()) {
    264           comp[bfs.nextNode()] = c;
    265           bfs.processNextNode();
    266         }
    267         ++c;
    268       }
    269     }
    270     return c;
    271   }
    272 
    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();
     1380    typedef typename UndirGraph::Node Node;
     1381    typedef typename UndirGraph::NodeIt NodeIt;
     1382    typedef typename UndirGraph::Edge Edge;
     1383    if (NodeIt(graph) == INVALID) return false;
     1384    Dfs<UndirGraph> dfs(graph);
     1385    dfs.init();
     1386    typename UndirGraph::template NodeMap<bool> red(graph);
    3291387    for (NodeIt it(graph); it != INVALID; ++it) {
    3301388      if (!dfs.reached(it)) {
    3311389        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 
     1390        red[it] = true;
     1391        while (!dfs.emptyQueue()) {
     1392          Edge edge = dfs.nextEdge();
     1393          Node source = graph.source(edge);
     1394          Node target = graph.target(edge);
     1395          if (dfs.reached(target) && red[source] == red[target]) {
     1396            return false;
     1397          } else {
     1398            red[target] = !red[source];
     1399          }
     1400          dfs.processNextEdge();
     1401        }
     1402      }
     1403    }
     1404    return true;
     1405  }
     1406   
    4191407} //namespace lemon
    4201408
Note: See TracChangeset for help on using the changeset viewer.