lemon/connectivity.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 12 Dec 2008 21:46:08 +0100
changeset 431 9dfaf6efc36f
child 419 9afe81e4c543
permissions -rw-r--r--
Hide all docs in variant.h (#196)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_TOPOLOGY_H
    20 #define LEMON_TOPOLOGY_H
    21 
    22 #include <lemon/dfs.h>
    23 #include <lemon/bfs.h>
    24 #include <lemon/core.h>
    25 #include <lemon/maps.h>
    26 #include <lemon/adaptors.h>
    27 
    28 #include <lemon/concepts/digraph.h>
    29 #include <lemon/concepts/graph.h>
    30 #include <lemon/concept_check.h>
    31 
    32 #include <stack>
    33 #include <functional>
    34 
    35 /// \ingroup connectivity
    36 /// \file
    37 /// \brief Connectivity algorithms
    38 ///
    39 /// Connectivity algorithms
    40 
    41 namespace lemon {
    42 
    43   /// \ingroup connectivity
    44   ///
    45   /// \brief Check whether the given undirected graph is connected.
    46   ///
    47   /// Check whether the given undirected graph is connected.
    48   /// \param graph The undirected graph.
    49   /// \return %True when there is path between any two nodes in the graph.
    50   /// \note By definition, the empty graph is connected.
    51   template <typename Graph>
    52   bool connected(const Graph& graph) {
    53     checkConcept<concepts::Graph, Graph>();
    54     typedef typename Graph::NodeIt NodeIt;
    55     if (NodeIt(graph) == INVALID) return true;
    56     Dfs<Graph> dfs(graph);
    57     dfs.run(NodeIt(graph));
    58     for (NodeIt it(graph); it != INVALID; ++it) {
    59       if (!dfs.reached(it)) {
    60         return false;
    61       }
    62     }
    63     return true;
    64   }
    65 
    66   /// \ingroup connectivity
    67   ///
    68   /// \brief Count the number of connected components of an undirected graph
    69   ///
    70   /// Count the number of connected components of an undirected graph
    71   ///
    72   /// \param graph The graph. It must be undirected.
    73   /// \return The number of components
    74   /// \note By definition, the empty graph consists
    75   /// of zero connected components.
    76   template <typename Graph>
    77   int countConnectedComponents(const Graph &graph) {
    78     checkConcept<concepts::Graph, Graph>();
    79     typedef typename Graph::Node Node;
    80     typedef typename Graph::Arc Arc;
    81 
    82     typedef NullMap<Node, Arc> PredMap;
    83     typedef NullMap<Node, int> DistMap;
    84 
    85     int compNum = 0;
    86     typename Bfs<Graph>::
    87       template SetPredMap<PredMap>::
    88       template SetDistMap<DistMap>::
    89       Create bfs(graph);
    90 
    91     PredMap predMap;
    92     bfs.predMap(predMap);
    93 
    94     DistMap distMap;
    95     bfs.distMap(distMap);
    96 
    97     bfs.init();
    98     for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
    99       if (!bfs.reached(n)) {
   100         bfs.addSource(n);
   101         bfs.start();
   102         ++compNum;
   103       }
   104     }
   105     return compNum;
   106   }
   107 
   108   /// \ingroup connectivity
   109   ///
   110   /// \brief Find the connected components of an undirected graph
   111   ///
   112   /// Find the connected components of an undirected graph.
   113   ///
   114   /// \param graph The graph. It must be undirected.
   115   /// \retval compMap A writable node map. The values will be set from 0 to
   116   /// the number of the connected components minus one. Each values of the map
   117   /// will be set exactly once, the values of a certain component will be
   118   /// set continuously.
   119   /// \return The number of components
   120   ///
   121   template <class Graph, class NodeMap>
   122   int connectedComponents(const Graph &graph, NodeMap &compMap) {
   123     checkConcept<concepts::Graph, Graph>();
   124     typedef typename Graph::Node Node;
   125     typedef typename Graph::Arc Arc;
   126     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
   127 
   128     typedef NullMap<Node, Arc> PredMap;
   129     typedef NullMap<Node, int> DistMap;
   130 
   131     int compNum = 0;
   132     typename Bfs<Graph>::
   133       template SetPredMap<PredMap>::
   134       template SetDistMap<DistMap>::
   135       Create bfs(graph);
   136 
   137     PredMap predMap;
   138     bfs.predMap(predMap);
   139 
   140     DistMap distMap;
   141     bfs.distMap(distMap);
   142 
   143     bfs.init();
   144     for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
   145       if(!bfs.reached(n)) {
   146         bfs.addSource(n);
   147         while (!bfs.emptyQueue()) {
   148           compMap.set(bfs.nextNode(), compNum);
   149           bfs.processNextNode();
   150         }
   151         ++compNum;
   152       }
   153     }
   154     return compNum;
   155   }
   156 
   157   namespace _topology_bits {
   158 
   159     template <typename Digraph, typename Iterator >
   160     struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
   161     public:
   162       typedef typename Digraph::Node Node;
   163       LeaveOrderVisitor(Iterator it) : _it(it) {}
   164 
   165       void leave(const Node& node) {
   166         *(_it++) = node;
   167       }
   168 
   169     private:
   170       Iterator _it;
   171     };
   172 
   173     template <typename Digraph, typename Map>
   174     struct FillMapVisitor : public DfsVisitor<Digraph> {
   175     public:
   176       typedef typename Digraph::Node Node;
   177       typedef typename Map::Value Value;
   178 
   179       FillMapVisitor(Map& map, Value& value)
   180         : _map(map), _value(value) {}
   181 
   182       void reach(const Node& node) {
   183         _map.set(node, _value);
   184       }
   185     private:
   186       Map& _map;
   187       Value& _value;
   188     };
   189 
   190     template <typename Digraph, typename ArcMap>
   191     struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
   192     public:
   193       typedef typename Digraph::Node Node;
   194       typedef typename Digraph::Arc Arc;
   195 
   196       StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
   197                                        ArcMap& cutMap,
   198                                        int& cutNum)
   199         : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
   200           _compMap(digraph), _num(0) {
   201       }
   202 
   203       void stop(const Node&) {
   204         ++_num;
   205       }
   206 
   207       void reach(const Node& node) {
   208         _compMap.set(node, _num);
   209       }
   210 
   211       void examine(const Arc& arc) {
   212          if (_compMap[_digraph.source(arc)] !=
   213              _compMap[_digraph.target(arc)]) {
   214            _cutMap.set(arc, true);
   215            ++_cutNum;
   216          }
   217       }
   218     private:
   219       const Digraph& _digraph;
   220       ArcMap& _cutMap;
   221       int& _cutNum;
   222 
   223       typename Digraph::template NodeMap<int> _compMap;
   224       int _num;
   225     };
   226 
   227   }
   228 
   229 
   230   /// \ingroup connectivity
   231   ///
   232   /// \brief Check whether the given directed graph is strongly connected.
   233   ///
   234   /// Check whether the given directed graph is strongly connected. The
   235   /// graph is strongly connected when any two nodes of the graph are
   236   /// connected with directed paths in both direction.
   237   /// \return %False when the graph is not strongly connected.
   238   /// \see connected
   239   ///
   240   /// \note By definition, the empty graph is strongly connected.
   241   template <typename Digraph>
   242   bool stronglyConnected(const Digraph& digraph) {
   243     checkConcept<concepts::Digraph, Digraph>();
   244 
   245     typedef typename Digraph::Node Node;
   246     typedef typename Digraph::NodeIt NodeIt;
   247 
   248     typename Digraph::Node source = NodeIt(digraph);
   249     if (source == INVALID) return true;
   250 
   251     using namespace _topology_bits;
   252 
   253     typedef DfsVisitor<Digraph> Visitor;
   254     Visitor visitor;
   255 
   256     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
   257     dfs.init();
   258     dfs.addSource(source);
   259     dfs.start();
   260 
   261     for (NodeIt it(digraph); it != INVALID; ++it) {
   262       if (!dfs.reached(it)) {
   263         return false;
   264       }
   265     }
   266 
   267     typedef ReverseDigraph<const Digraph> RDigraph;
   268     RDigraph rdigraph(digraph);
   269 
   270     typedef DfsVisitor<Digraph> RVisitor;
   271     RVisitor rvisitor;
   272 
   273     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   274     rdfs.init();
   275     rdfs.addSource(source);
   276     rdfs.start();
   277 
   278     for (NodeIt it(rdigraph); it != INVALID; ++it) {
   279       if (!rdfs.reached(it)) {
   280         return false;
   281       }
   282     }
   283 
   284     return true;
   285   }
   286 
   287   /// \ingroup connectivity
   288   ///
   289   /// \brief Count the strongly connected components of a directed graph
   290   ///
   291   /// Count the strongly connected components of a directed graph.
   292   /// The strongly connected components are the classes of an
   293   /// equivalence relation on the nodes of the graph. Two nodes are in
   294   /// the same class if they are connected with directed paths in both
   295   /// direction.
   296   ///
   297   /// \param graph The graph.
   298   /// \return The number of components
   299   /// \note By definition, the empty graph has zero
   300   /// strongly connected components.
   301   template <typename Digraph>
   302   int countStronglyConnectedComponents(const Digraph& digraph) {
   303     checkConcept<concepts::Digraph, Digraph>();
   304 
   305     using namespace _topology_bits;
   306 
   307     typedef typename Digraph::Node Node;
   308     typedef typename Digraph::Arc Arc;
   309     typedef typename Digraph::NodeIt NodeIt;
   310     typedef typename Digraph::ArcIt ArcIt;
   311 
   312     typedef std::vector<Node> Container;
   313     typedef typename Container::iterator Iterator;
   314 
   315     Container nodes(countNodes(digraph));
   316     typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
   317     Visitor visitor(nodes.begin());
   318 
   319     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
   320     dfs.init();
   321     for (NodeIt it(digraph); it != INVALID; ++it) {
   322       if (!dfs.reached(it)) {
   323         dfs.addSource(it);
   324         dfs.start();
   325       }
   326     }
   327 
   328     typedef typename Container::reverse_iterator RIterator;
   329     typedef ReverseDigraph<const Digraph> RDigraph;
   330 
   331     RDigraph rdigraph(digraph);
   332 
   333     typedef DfsVisitor<Digraph> RVisitor;
   334     RVisitor rvisitor;
   335 
   336     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   337 
   338     int compNum = 0;
   339 
   340     rdfs.init();
   341     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   342       if (!rdfs.reached(*it)) {
   343         rdfs.addSource(*it);
   344         rdfs.start();
   345         ++compNum;
   346       }
   347     }
   348     return compNum;
   349   }
   350 
   351   /// \ingroup connectivity
   352   ///
   353   /// \brief Find the strongly connected components of a directed graph
   354   ///
   355   /// Find the strongly connected components of a directed graph.  The
   356   /// strongly connected components are the classes of an equivalence
   357   /// relation on the nodes of the graph. Two nodes are in
   358   /// relationship when there are directed paths between them in both
   359   /// direction. In addition, the numbering of components will satisfy
   360   /// that there is no arc going from a higher numbered component to
   361   /// a lower.
   362   ///
   363   /// \param digraph The digraph.
   364   /// \retval compMap A writable node map. The values will be set from 0 to
   365   /// the number of the strongly connected components minus one. Each value
   366   /// of the map will be set exactly once, the values of a certain component
   367   /// will be set continuously.
   368   /// \return The number of components
   369   ///
   370   template <typename Digraph, typename NodeMap>
   371   int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
   372     checkConcept<concepts::Digraph, Digraph>();
   373     typedef typename Digraph::Node Node;
   374     typedef typename Digraph::NodeIt NodeIt;
   375     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
   376 
   377     using namespace _topology_bits;
   378 
   379     typedef std::vector<Node> Container;
   380     typedef typename Container::iterator Iterator;
   381 
   382     Container nodes(countNodes(digraph));
   383     typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
   384     Visitor visitor(nodes.begin());
   385 
   386     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
   387     dfs.init();
   388     for (NodeIt it(digraph); it != INVALID; ++it) {
   389       if (!dfs.reached(it)) {
   390         dfs.addSource(it);
   391         dfs.start();
   392       }
   393     }
   394 
   395     typedef typename Container::reverse_iterator RIterator;
   396     typedef ReverseDigraph<const Digraph> RDigraph;
   397 
   398     RDigraph rdigraph(digraph);
   399 
   400     int compNum = 0;
   401 
   402     typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
   403     RVisitor rvisitor(compMap, compNum);
   404 
   405     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   406 
   407     rdfs.init();
   408     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   409       if (!rdfs.reached(*it)) {
   410         rdfs.addSource(*it);
   411         rdfs.start();
   412         ++compNum;
   413       }
   414     }
   415     return compNum;
   416   }
   417 
   418   /// \ingroup connectivity
   419   ///
   420   /// \brief Find the cut arcs of the strongly connected components.
   421   ///
   422   /// Find the cut arcs of the strongly connected components.
   423   /// The strongly connected components are the classes of an equivalence
   424   /// relation on the nodes of the graph. Two nodes are in relationship
   425   /// when there are directed paths between them in both direction.
   426   /// The strongly connected components are separated by the cut arcs.
   427   ///
   428   /// \param graph The graph.
   429   /// \retval cutMap A writable node map. The values will be set true when the
   430   /// arc is a cut arc.
   431   ///
   432   /// \return The number of cut arcs
   433   template <typename Digraph, typename ArcMap>
   434   int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
   435     checkConcept<concepts::Digraph, Digraph>();
   436     typedef typename Digraph::Node Node;
   437     typedef typename Digraph::Arc Arc;
   438     typedef typename Digraph::NodeIt NodeIt;
   439     checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
   440 
   441     using namespace _topology_bits;
   442 
   443     typedef std::vector<Node> Container;
   444     typedef typename Container::iterator Iterator;
   445 
   446     Container nodes(countNodes(graph));
   447     typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
   448     Visitor visitor(nodes.begin());
   449 
   450     DfsVisit<Digraph, Visitor> dfs(graph, visitor);
   451     dfs.init();
   452     for (NodeIt it(graph); it != INVALID; ++it) {
   453       if (!dfs.reached(it)) {
   454         dfs.addSource(it);
   455         dfs.start();
   456       }
   457     }
   458 
   459     typedef typename Container::reverse_iterator RIterator;
   460     typedef ReverseDigraph<const Digraph> RDigraph;
   461 
   462     RDigraph rgraph(graph);
   463 
   464     int cutNum = 0;
   465 
   466     typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
   467     RVisitor rvisitor(rgraph, cutMap, cutNum);
   468 
   469     DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
   470 
   471     rdfs.init();
   472     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   473       if (!rdfs.reached(*it)) {
   474         rdfs.addSource(*it);
   475         rdfs.start();
   476       }
   477     }
   478     return cutNum;
   479   }
   480 
   481   namespace _topology_bits {
   482 
   483     template <typename Digraph>
   484     class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   485     public:
   486       typedef typename Digraph::Node Node;
   487       typedef typename Digraph::Arc Arc;
   488       typedef typename Digraph::Edge Edge;
   489 
   490       CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
   491         : _graph(graph), _compNum(compNum),
   492           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   493 
   494       void start(const Node& node) {
   495         _predMap.set(node, INVALID);
   496       }
   497 
   498       void reach(const Node& node) {
   499         _numMap.set(node, _num);
   500         _retMap.set(node, _num);
   501         ++_num;
   502       }
   503 
   504       void discover(const Arc& edge) {
   505         _predMap.set(_graph.target(edge), _graph.source(edge));
   506       }
   507 
   508       void examine(const Arc& edge) {
   509         if (_graph.source(edge) == _graph.target(edge) &&
   510             _graph.direction(edge)) {
   511           ++_compNum;
   512           return;
   513         }
   514         if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
   515           return;
   516         }
   517         if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
   518           _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
   519         }
   520       }
   521 
   522       void backtrack(const Arc& edge) {
   523         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   524           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   525         }
   526         if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
   527           ++_compNum;
   528         }
   529       }
   530 
   531     private:
   532       const Digraph& _graph;
   533       int& _compNum;
   534 
   535       typename Digraph::template NodeMap<int> _numMap;
   536       typename Digraph::template NodeMap<int> _retMap;
   537       typename Digraph::template NodeMap<Node> _predMap;
   538       int _num;
   539     };
   540 
   541     template <typename Digraph, typename ArcMap>
   542     class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   543     public:
   544       typedef typename Digraph::Node Node;
   545       typedef typename Digraph::Arc Arc;
   546       typedef typename Digraph::Edge Edge;
   547 
   548       BiNodeConnectedComponentsVisitor(const Digraph& graph,
   549                                        ArcMap& compMap, int &compNum)
   550         : _graph(graph), _compMap(compMap), _compNum(compNum),
   551           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   552 
   553       void start(const Node& node) {
   554         _predMap.set(node, INVALID);
   555       }
   556 
   557       void reach(const Node& node) {
   558         _numMap.set(node, _num);
   559         _retMap.set(node, _num);
   560         ++_num;
   561       }
   562 
   563       void discover(const Arc& edge) {
   564         Node target = _graph.target(edge);
   565         _predMap.set(target, edge);
   566         _edgeStack.push(edge);
   567       }
   568 
   569       void examine(const Arc& edge) {
   570         Node source = _graph.source(edge);
   571         Node target = _graph.target(edge);
   572         if (source == target && _graph.direction(edge)) {
   573           _compMap.set(edge, _compNum);
   574           ++_compNum;
   575           return;
   576         }
   577         if (_numMap[target] < _numMap[source]) {
   578           if (_predMap[source] != _graph.oppositeArc(edge)) {
   579             _edgeStack.push(edge);
   580           }
   581         }
   582         if (_predMap[source] != INVALID &&
   583             target == _graph.source(_predMap[source])) {
   584           return;
   585         }
   586         if (_retMap[source] > _numMap[target]) {
   587           _retMap.set(source, _numMap[target]);
   588         }
   589       }
   590 
   591       void backtrack(const Arc& edge) {
   592         Node source = _graph.source(edge);
   593         Node target = _graph.target(edge);
   594         if (_retMap[source] > _retMap[target]) {
   595           _retMap.set(source, _retMap[target]);
   596         }
   597         if (_numMap[source] <= _retMap[target]) {
   598           while (_edgeStack.top() != edge) {
   599             _compMap.set(_edgeStack.top(), _compNum);
   600             _edgeStack.pop();
   601           }
   602           _compMap.set(edge, _compNum);
   603           _edgeStack.pop();
   604           ++_compNum;
   605         }
   606       }
   607 
   608     private:
   609       const Digraph& _graph;
   610       ArcMap& _compMap;
   611       int& _compNum;
   612 
   613       typename Digraph::template NodeMap<int> _numMap;
   614       typename Digraph::template NodeMap<int> _retMap;
   615       typename Digraph::template NodeMap<Arc> _predMap;
   616       std::stack<Edge> _edgeStack;
   617       int _num;
   618     };
   619 
   620 
   621     template <typename Digraph, typename NodeMap>
   622     class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
   623     public:
   624       typedef typename Digraph::Node Node;
   625       typedef typename Digraph::Arc Arc;
   626       typedef typename Digraph::Edge Edge;
   627 
   628       BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap,
   629                                      int& cutNum)
   630         : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
   631           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   632 
   633       void start(const Node& node) {
   634         _predMap.set(node, INVALID);
   635         rootCut = false;
   636       }
   637 
   638       void reach(const Node& node) {
   639         _numMap.set(node, _num);
   640         _retMap.set(node, _num);
   641         ++_num;
   642       }
   643 
   644       void discover(const Arc& edge) {
   645         _predMap.set(_graph.target(edge), _graph.source(edge));
   646       }
   647 
   648       void examine(const Arc& edge) {
   649         if (_graph.source(edge) == _graph.target(edge) &&
   650             _graph.direction(edge)) {
   651           if (!_cutMap[_graph.source(edge)]) {
   652             _cutMap.set(_graph.source(edge), true);
   653             ++_cutNum;
   654           }
   655           return;
   656         }
   657         if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
   658         if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
   659           _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
   660         }
   661       }
   662 
   663       void backtrack(const Arc& edge) {
   664         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   665           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   666         }
   667         if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
   668           if (_predMap[_graph.source(edge)] != INVALID) {
   669             if (!_cutMap[_graph.source(edge)]) {
   670               _cutMap.set(_graph.source(edge), true);
   671               ++_cutNum;
   672             }
   673           } else if (rootCut) {
   674             if (!_cutMap[_graph.source(edge)]) {
   675               _cutMap.set(_graph.source(edge), true);
   676               ++_cutNum;
   677             }
   678           } else {
   679             rootCut = true;
   680           }
   681         }
   682       }
   683 
   684     private:
   685       const Digraph& _graph;
   686       NodeMap& _cutMap;
   687       int& _cutNum;
   688 
   689       typename Digraph::template NodeMap<int> _numMap;
   690       typename Digraph::template NodeMap<int> _retMap;
   691       typename Digraph::template NodeMap<Node> _predMap;
   692       std::stack<Edge> _edgeStack;
   693       int _num;
   694       bool rootCut;
   695     };
   696 
   697   }
   698 
   699   template <typename Graph>
   700   int countBiNodeConnectedComponents(const Graph& graph);
   701 
   702   /// \ingroup connectivity
   703   ///
   704   /// \brief Checks the graph is bi-node-connected.
   705   ///
   706   /// This function checks that the undirected graph is bi-node-connected
   707   /// graph. The graph is bi-node-connected if any two undirected edge is
   708   /// on same circle.
   709   ///
   710   /// \param graph The graph.
   711   /// \return %True when the graph bi-node-connected.
   712   template <typename Graph>
   713   bool biNodeConnected(const Graph& graph) {
   714     return countBiNodeConnectedComponents(graph) <= 1;
   715   }
   716 
   717   /// \ingroup connectivity
   718   ///
   719   /// \brief Count the biconnected components.
   720   ///
   721   /// This function finds the bi-node-connected components in an undirected
   722   /// graph. The biconnected components are the classes of an equivalence
   723   /// relation on the undirected edges. Two undirected edge is in relationship
   724   /// when they are on same circle.
   725   ///
   726   /// \param graph The graph.
   727   /// \return The number of components.
   728   template <typename Graph>
   729   int countBiNodeConnectedComponents(const Graph& graph) {
   730     checkConcept<concepts::Graph, Graph>();
   731     typedef typename Graph::NodeIt NodeIt;
   732 
   733     using namespace _topology_bits;
   734 
   735     typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
   736 
   737     int compNum = 0;
   738     Visitor visitor(graph, compNum);
   739 
   740     DfsVisit<Graph, Visitor> dfs(graph, visitor);
   741     dfs.init();
   742 
   743     for (NodeIt it(graph); it != INVALID; ++it) {
   744       if (!dfs.reached(it)) {
   745         dfs.addSource(it);
   746         dfs.start();
   747       }
   748     }
   749     return compNum;
   750   }
   751 
   752   /// \ingroup connectivity
   753   ///
   754   /// \brief Find the bi-node-connected components.
   755   ///
   756   /// This function finds the bi-node-connected components in an undirected
   757   /// graph. The bi-node-connected components are the classes of an equivalence
   758   /// relation on the undirected edges. Two undirected edge are in relationship
   759   /// when they are on same circle.
   760   ///
   761   /// \param graph The graph.
   762   /// \retval compMap A writable uedge map. The values will be set from 0
   763   /// to the number of the biconnected components minus one. Each values
   764   /// of the map will be set exactly once, the values of a certain component
   765   /// will be set continuously.
   766   /// \return The number of components.
   767   ///
   768   template <typename Graph, typename EdgeMap>
   769   int biNodeConnectedComponents(const Graph& graph,
   770                                 EdgeMap& compMap) {
   771     checkConcept<concepts::Graph, Graph>();
   772     typedef typename Graph::NodeIt NodeIt;
   773     typedef typename Graph::Edge Edge;
   774     checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
   775 
   776     using namespace _topology_bits;
   777 
   778     typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
   779 
   780     int compNum = 0;
   781     Visitor visitor(graph, compMap, compNum);
   782 
   783     DfsVisit<Graph, Visitor> dfs(graph, visitor);
   784     dfs.init();
   785 
   786     for (NodeIt it(graph); it != INVALID; ++it) {
   787       if (!dfs.reached(it)) {
   788         dfs.addSource(it);
   789         dfs.start();
   790       }
   791     }
   792     return compNum;
   793   }
   794 
   795   /// \ingroup connectivity
   796   ///
   797   /// \brief Find the bi-node-connected cut nodes.
   798   ///
   799   /// This function finds the bi-node-connected cut nodes in an undirected
   800   /// graph. The bi-node-connected components are the classes of an equivalence
   801   /// relation on the undirected edges. Two undirected edges are in
   802   /// relationship when they are on same circle. The biconnected components
   803   /// are separted by nodes which are the cut nodes of the components.
   804   ///
   805   /// \param graph The graph.
   806   /// \retval cutMap A writable edge map. The values will be set true when
   807   /// the node separate two or more components.
   808   /// \return The number of the cut nodes.
   809   template <typename Graph, typename NodeMap>
   810   int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
   811     checkConcept<concepts::Graph, Graph>();
   812     typedef typename Graph::Node Node;
   813     typedef typename Graph::NodeIt NodeIt;
   814     checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
   815 
   816     using namespace _topology_bits;
   817 
   818     typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
   819 
   820     int cutNum = 0;
   821     Visitor visitor(graph, cutMap, cutNum);
   822 
   823     DfsVisit<Graph, Visitor> dfs(graph, visitor);
   824     dfs.init();
   825 
   826     for (NodeIt it(graph); it != INVALID; ++it) {
   827       if (!dfs.reached(it)) {
   828         dfs.addSource(it);
   829         dfs.start();
   830       }
   831     }
   832     return cutNum;
   833   }
   834 
   835   namespace _topology_bits {
   836 
   837     template <typename Digraph>
   838     class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   839     public:
   840       typedef typename Digraph::Node Node;
   841       typedef typename Digraph::Arc Arc;
   842       typedef typename Digraph::Edge Edge;
   843 
   844       CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
   845         : _graph(graph), _compNum(compNum),
   846           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   847 
   848       void start(const Node& node) {
   849         _predMap.set(node, INVALID);
   850       }
   851 
   852       void reach(const Node& node) {
   853         _numMap.set(node, _num);
   854         _retMap.set(node, _num);
   855         ++_num;
   856       }
   857 
   858       void leave(const Node& node) {
   859         if (_numMap[node] <= _retMap[node]) {
   860           ++_compNum;
   861         }
   862       }
   863 
   864       void discover(const Arc& edge) {
   865         _predMap.set(_graph.target(edge), edge);
   866       }
   867 
   868       void examine(const Arc& edge) {
   869         if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
   870           return;
   871         }
   872         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   873           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   874         }
   875       }
   876 
   877       void backtrack(const Arc& edge) {
   878         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   879           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   880         }
   881       }
   882 
   883     private:
   884       const Digraph& _graph;
   885       int& _compNum;
   886 
   887       typename Digraph::template NodeMap<int> _numMap;
   888       typename Digraph::template NodeMap<int> _retMap;
   889       typename Digraph::template NodeMap<Arc> _predMap;
   890       int _num;
   891     };
   892 
   893     template <typename Digraph, typename NodeMap>
   894     class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   895     public:
   896       typedef typename Digraph::Node Node;
   897       typedef typename Digraph::Arc Arc;
   898       typedef typename Digraph::Edge Edge;
   899 
   900       BiEdgeConnectedComponentsVisitor(const Digraph& graph,
   901                                        NodeMap& compMap, int &compNum)
   902         : _graph(graph), _compMap(compMap), _compNum(compNum),
   903           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   904 
   905       void start(const Node& node) {
   906         _predMap.set(node, INVALID);
   907       }
   908 
   909       void reach(const Node& node) {
   910         _numMap.set(node, _num);
   911         _retMap.set(node, _num);
   912         _nodeStack.push(node);
   913         ++_num;
   914       }
   915 
   916       void leave(const Node& node) {
   917         if (_numMap[node] <= _retMap[node]) {
   918           while (_nodeStack.top() != node) {
   919             _compMap.set(_nodeStack.top(), _compNum);
   920             _nodeStack.pop();
   921           }
   922           _compMap.set(node, _compNum);
   923           _nodeStack.pop();
   924           ++_compNum;
   925         }
   926       }
   927 
   928       void discover(const Arc& edge) {
   929         _predMap.set(_graph.target(edge), edge);
   930       }
   931 
   932       void examine(const Arc& edge) {
   933         if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
   934           return;
   935         }
   936         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   937           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   938         }
   939       }
   940 
   941       void backtrack(const Arc& edge) {
   942         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   943           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   944         }
   945       }
   946 
   947     private:
   948       const Digraph& _graph;
   949       NodeMap& _compMap;
   950       int& _compNum;
   951 
   952       typename Digraph::template NodeMap<int> _numMap;
   953       typename Digraph::template NodeMap<int> _retMap;
   954       typename Digraph::template NodeMap<Arc> _predMap;
   955       std::stack<Node> _nodeStack;
   956       int _num;
   957     };
   958 
   959 
   960     template <typename Digraph, typename ArcMap>
   961     class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
   962     public:
   963       typedef typename Digraph::Node Node;
   964       typedef typename Digraph::Arc Arc;
   965       typedef typename Digraph::Edge Edge;
   966 
   967       BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
   968                                      ArcMap& cutMap, int &cutNum)
   969         : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
   970           _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   971 
   972       void start(const Node& node) {
   973         _predMap[node] = INVALID;
   974       }
   975 
   976       void reach(const Node& node) {
   977         _numMap.set(node, _num);
   978         _retMap.set(node, _num);
   979         ++_num;
   980       }
   981 
   982       void leave(const Node& node) {
   983         if (_numMap[node] <= _retMap[node]) {
   984           if (_predMap[node] != INVALID) {
   985             _cutMap.set(_predMap[node], true);
   986             ++_cutNum;
   987           }
   988         }
   989       }
   990 
   991       void discover(const Arc& edge) {
   992         _predMap.set(_graph.target(edge), edge);
   993       }
   994 
   995       void examine(const Arc& edge) {
   996         if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
   997           return;
   998         }
   999         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
  1000           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
  1001         }
  1002       }
  1003 
  1004       void backtrack(const Arc& edge) {
  1005         if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
  1006           _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
  1007         }
  1008       }
  1009 
  1010     private:
  1011       const Digraph& _graph;
  1012       ArcMap& _cutMap;
  1013       int& _cutNum;
  1014 
  1015       typename Digraph::template NodeMap<int> _numMap;
  1016       typename Digraph::template NodeMap<int> _retMap;
  1017       typename Digraph::template NodeMap<Arc> _predMap;
  1018       int _num;
  1019     };
  1020   }
  1021 
  1022   template <typename Graph>
  1023   int countBiEdgeConnectedComponents(const Graph& graph);
  1024 
  1025   /// \ingroup connectivity
  1026   ///
  1027   /// \brief Checks that the graph is bi-edge-connected.
  1028   ///
  1029   /// This function checks that the graph is bi-edge-connected. The undirected
  1030   /// graph is bi-edge-connected when any two nodes are connected with two
  1031   /// edge-disjoint paths.
  1032   ///
  1033   /// \param graph The undirected graph.
  1034   /// \return The number of components.
  1035   template <typename Graph>
  1036   bool biEdgeConnected(const Graph& graph) {
  1037     return countBiEdgeConnectedComponents(graph) <= 1;
  1038   }
  1039 
  1040   /// \ingroup connectivity
  1041   ///
  1042   /// \brief Count the bi-edge-connected components.
  1043   ///
  1044   /// This function count the bi-edge-connected components in an undirected
  1045   /// graph. The bi-edge-connected components are the classes of an equivalence
  1046   /// relation on the nodes. Two nodes are in relationship when they are
  1047   /// connected with at least two edge-disjoint paths.
  1048   ///
  1049   /// \param graph The undirected graph.
  1050   /// \return The number of components.
  1051   template <typename Graph>
  1052   int countBiEdgeConnectedComponents(const Graph& graph) {
  1053     checkConcept<concepts::Graph, Graph>();
  1054     typedef typename Graph::NodeIt NodeIt;
  1055 
  1056     using namespace _topology_bits;
  1057 
  1058     typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
  1059 
  1060     int compNum = 0;
  1061     Visitor visitor(graph, compNum);
  1062 
  1063     DfsVisit<Graph, Visitor> dfs(graph, visitor);
  1064     dfs.init();
  1065 
  1066     for (NodeIt it(graph); it != INVALID; ++it) {
  1067       if (!dfs.reached(it)) {
  1068         dfs.addSource(it);
  1069         dfs.start();
  1070       }
  1071     }
  1072     return compNum;
  1073   }
  1074 
  1075   /// \ingroup connectivity
  1076   ///
  1077   /// \brief Find the bi-edge-connected components.
  1078   ///
  1079   /// This function finds the bi-edge-connected components in an undirected
  1080   /// graph. The bi-edge-connected components are the classes of an equivalence
  1081   /// relation on the nodes. Two nodes are in relationship when they are
  1082   /// connected at least two edge-disjoint paths.
  1083   ///
  1084   /// \param graph The graph.
  1085   /// \retval compMap A writable node map. The values will be set from 0 to
  1086   /// the number of the biconnected components minus one. Each values
  1087   /// of the map will be set exactly once, the values of a certain component
  1088   /// will be set continuously.
  1089   /// \return The number of components.
  1090   ///
  1091   template <typename Graph, typename NodeMap>
  1092   int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
  1093     checkConcept<concepts::Graph, Graph>();
  1094     typedef typename Graph::NodeIt NodeIt;
  1095     typedef typename Graph::Node Node;
  1096     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
  1097 
  1098     using namespace _topology_bits;
  1099 
  1100     typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
  1101 
  1102     int compNum = 0;
  1103     Visitor visitor(graph, compMap, compNum);
  1104 
  1105     DfsVisit<Graph, Visitor> dfs(graph, visitor);
  1106     dfs.init();
  1107 
  1108     for (NodeIt it(graph); it != INVALID; ++it) {
  1109       if (!dfs.reached(it)) {
  1110         dfs.addSource(it);
  1111         dfs.start();
  1112       }
  1113     }
  1114     return compNum;
  1115   }
  1116 
  1117   /// \ingroup connectivity
  1118   ///
  1119   /// \brief Find the bi-edge-connected cut edges.
  1120   ///
  1121   /// This function finds the bi-edge-connected components in an undirected
  1122   /// graph. The bi-edge-connected components are the classes of an equivalence
  1123   /// relation on the nodes. Two nodes are in relationship when they are
  1124   /// connected with at least two edge-disjoint paths. The bi-edge-connected
  1125   /// components are separted by edges which are the cut edges of the
  1126   /// components.
  1127   ///
  1128   /// \param graph The graph.
  1129   /// \retval cutMap A writable node map. The values will be set true when the
  1130   /// edge is a cut edge.
  1131   /// \return The number of cut edges.
  1132   template <typename Graph, typename EdgeMap>
  1133   int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
  1134     checkConcept<concepts::Graph, Graph>();
  1135     typedef typename Graph::NodeIt NodeIt;
  1136     typedef typename Graph::Edge Edge;
  1137     checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
  1138 
  1139     using namespace _topology_bits;
  1140 
  1141     typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
  1142 
  1143     int cutNum = 0;
  1144     Visitor visitor(graph, cutMap, cutNum);
  1145 
  1146     DfsVisit<Graph, Visitor> dfs(graph, visitor);
  1147     dfs.init();
  1148 
  1149     for (NodeIt it(graph); it != INVALID; ++it) {
  1150       if (!dfs.reached(it)) {
  1151         dfs.addSource(it);
  1152         dfs.start();
  1153       }
  1154     }
  1155     return cutNum;
  1156   }
  1157 
  1158 
  1159   namespace _topology_bits {
  1160 
  1161     template <typename Digraph, typename IntNodeMap>
  1162     class TopologicalSortVisitor : public DfsVisitor<Digraph> {
  1163     public:
  1164       typedef typename Digraph::Node Node;
  1165       typedef typename Digraph::Arc edge;
  1166 
  1167       TopologicalSortVisitor(IntNodeMap& order, int num)
  1168         : _order(order), _num(num) {}
  1169 
  1170       void leave(const Node& node) {
  1171         _order.set(node, --_num);
  1172       }
  1173 
  1174     private:
  1175       IntNodeMap& _order;
  1176       int _num;
  1177     };
  1178 
  1179   }
  1180 
  1181   /// \ingroup connectivity
  1182   ///
  1183   /// \brief Sort the nodes of a DAG into topolgical order.
  1184   ///
  1185   /// Sort the nodes of a DAG into topolgical order.
  1186   ///
  1187   /// \param graph The graph. It must be directed and acyclic.
  1188   /// \retval order A writable node map. The values will be set from 0 to
  1189   /// the number of the nodes in the graph minus one. Each values of the map
  1190   /// will be set exactly once, the values  will be set descending order.
  1191   ///
  1192   /// \see checkedTopologicalSort
  1193   /// \see dag
  1194   template <typename Digraph, typename NodeMap>
  1195   void topologicalSort(const Digraph& graph, NodeMap& order) {
  1196     using namespace _topology_bits;
  1197 
  1198     checkConcept<concepts::Digraph, Digraph>();
  1199     checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
  1200 
  1201     typedef typename Digraph::Node Node;
  1202     typedef typename Digraph::NodeIt NodeIt;
  1203     typedef typename Digraph::Arc Arc;
  1204 
  1205     TopologicalSortVisitor<Digraph, NodeMap>
  1206       visitor(order, countNodes(graph));
  1207 
  1208     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
  1209       dfs(graph, visitor);
  1210 
  1211     dfs.init();
  1212     for (NodeIt it(graph); it != INVALID; ++it) {
  1213       if (!dfs.reached(it)) {
  1214         dfs.addSource(it);
  1215         dfs.start();
  1216       }
  1217     }
  1218   }
  1219 
  1220   /// \ingroup connectivity
  1221   ///
  1222   /// \brief Sort the nodes of a DAG into topolgical order.
  1223   ///
  1224   /// Sort the nodes of a DAG into topolgical order. It also checks
  1225   /// that the given graph is DAG.
  1226   ///
  1227   /// \param graph The graph. It must be directed and acyclic.
  1228   /// \retval order A readable - writable node map. The values will be set
  1229   /// from 0 to the number of the nodes in the graph minus one. Each values
  1230   /// of the map will be set exactly once, the values will be set descending
  1231   /// order.
  1232   /// \return %False when the graph is not DAG.
  1233   ///
  1234   /// \see topologicalSort
  1235   /// \see dag
  1236   template <typename Digraph, typename NodeMap>
  1237   bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {
  1238     using namespace _topology_bits;
  1239 
  1240     checkConcept<concepts::Digraph, Digraph>();
  1241     checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
  1242       NodeMap>();
  1243 
  1244     typedef typename Digraph::Node Node;
  1245     typedef typename Digraph::NodeIt NodeIt;
  1246     typedef typename Digraph::Arc Arc;
  1247 
  1248     order = constMap<Node, int, -1>();
  1249 
  1250     TopologicalSortVisitor<Digraph, NodeMap>
  1251       visitor(order, countNodes(graph));
  1252 
  1253     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
  1254       dfs(graph, visitor);
  1255 
  1256     dfs.init();
  1257     for (NodeIt it(graph); it != INVALID; ++it) {
  1258       if (!dfs.reached(it)) {
  1259         dfs.addSource(it);
  1260         while (!dfs.emptyQueue()) {
  1261            Arc edge = dfs.nextArc();
  1262            Node target = graph.target(edge);
  1263            if (dfs.reached(target) && order[target] == -1) {
  1264              return false;
  1265            }
  1266            dfs.processNextArc();
  1267          }
  1268       }
  1269     }
  1270     return true;
  1271   }
  1272 
  1273   /// \ingroup connectivity
  1274   ///
  1275   /// \brief Check that the given directed graph is a DAG.
  1276   ///
  1277   /// Check that the given directed graph is a DAG. The DAG is
  1278   /// an Directed Acyclic Digraph.
  1279   /// \return %False when the graph is not DAG.
  1280   /// \see acyclic
  1281   template <typename Digraph>
  1282   bool dag(const Digraph& graph) {
  1283 
  1284     checkConcept<concepts::Digraph, Digraph>();
  1285 
  1286     typedef typename Digraph::Node Node;
  1287     typedef typename Digraph::NodeIt NodeIt;
  1288     typedef typename Digraph::Arc Arc;
  1289 
  1290     typedef typename Digraph::template NodeMap<bool> ProcessedMap;
  1291 
  1292     typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
  1293       Create dfs(graph);
  1294 
  1295     ProcessedMap processed(graph);
  1296     dfs.processedMap(processed);
  1297 
  1298     dfs.init();
  1299     for (NodeIt it(graph); it != INVALID; ++it) {
  1300       if (!dfs.reached(it)) {
  1301         dfs.addSource(it);
  1302         while (!dfs.emptyQueue()) {
  1303           Arc edge = dfs.nextArc();
  1304           Node target = graph.target(edge);
  1305           if (dfs.reached(target) && !processed[target]) {
  1306             return false;
  1307           }
  1308           dfs.processNextArc();
  1309         }
  1310       }
  1311     }
  1312     return true;
  1313   }
  1314 
  1315   /// \ingroup connectivity
  1316   ///
  1317   /// \brief Check that the given undirected graph is acyclic.
  1318   ///
  1319   /// Check that the given undirected graph acyclic.
  1320   /// \param graph The undirected graph.
  1321   /// \return %True when there is no circle in the graph.
  1322   /// \see dag
  1323   template <typename Graph>
  1324   bool acyclic(const Graph& graph) {
  1325     checkConcept<concepts::Graph, Graph>();
  1326     typedef typename Graph::Node Node;
  1327     typedef typename Graph::NodeIt NodeIt;
  1328     typedef typename Graph::Arc Arc;
  1329     Dfs<Graph> dfs(graph);
  1330     dfs.init();
  1331     for (NodeIt it(graph); it != INVALID; ++it) {
  1332       if (!dfs.reached(it)) {
  1333         dfs.addSource(it);
  1334         while (!dfs.emptyQueue()) {
  1335           Arc edge = dfs.nextArc();
  1336           Node source = graph.source(edge);
  1337           Node target = graph.target(edge);
  1338           if (dfs.reached(target) &&
  1339               dfs.predArc(source) != graph.oppositeArc(edge)) {
  1340             return false;
  1341           }
  1342           dfs.processNextArc();
  1343         }
  1344       }
  1345     }
  1346     return true;
  1347   }
  1348 
  1349   /// \ingroup connectivity
  1350   ///
  1351   /// \brief Check that the given undirected graph is tree.
  1352   ///
  1353   /// Check that the given undirected graph is tree.
  1354   /// \param graph The undirected graph.
  1355   /// \return %True when the graph is acyclic and connected.
  1356   template <typename Graph>
  1357   bool tree(const Graph& graph) {
  1358     checkConcept<concepts::Graph, Graph>();
  1359     typedef typename Graph::Node Node;
  1360     typedef typename Graph::NodeIt NodeIt;
  1361     typedef typename Graph::Arc Arc;
  1362     Dfs<Graph> dfs(graph);
  1363     dfs.init();
  1364     dfs.addSource(NodeIt(graph));
  1365     while (!dfs.emptyQueue()) {
  1366       Arc edge = dfs.nextArc();
  1367       Node source = graph.source(edge);
  1368       Node target = graph.target(edge);
  1369       if (dfs.reached(target) &&
  1370           dfs.predArc(source) != graph.oppositeArc(edge)) {
  1371         return false;
  1372       }
  1373       dfs.processNextArc();
  1374     }
  1375     for (NodeIt it(graph); it != INVALID; ++it) {
  1376       if (!dfs.reached(it)) {
  1377         return false;
  1378       }
  1379     }
  1380     return true;
  1381   }
  1382 
  1383   namespace _topology_bits {
  1384 
  1385     template <typename Digraph>
  1386     class BipartiteVisitor : public BfsVisitor<Digraph> {
  1387     public:
  1388       typedef typename Digraph::Arc Arc;
  1389       typedef typename Digraph::Node Node;
  1390 
  1391       BipartiteVisitor(const Digraph& graph, bool& bipartite)
  1392         : _graph(graph), _part(graph), _bipartite(bipartite) {}
  1393 
  1394       void start(const Node& node) {
  1395         _part[node] = true;
  1396       }
  1397       void discover(const Arc& edge) {
  1398         _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
  1399       }
  1400       void examine(const Arc& edge) {
  1401         _bipartite = _bipartite &&
  1402           _part[_graph.target(edge)] != _part[_graph.source(edge)];
  1403       }
  1404 
  1405     private:
  1406 
  1407       const Digraph& _graph;
  1408       typename Digraph::template NodeMap<bool> _part;
  1409       bool& _bipartite;
  1410     };
  1411 
  1412     template <typename Digraph, typename PartMap>
  1413     class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
  1414     public:
  1415       typedef typename Digraph::Arc Arc;
  1416       typedef typename Digraph::Node Node;
  1417 
  1418       BipartitePartitionsVisitor(const Digraph& graph,
  1419                                  PartMap& part, bool& bipartite)
  1420         : _graph(graph), _part(part), _bipartite(bipartite) {}
  1421 
  1422       void start(const Node& node) {
  1423         _part.set(node, true);
  1424       }
  1425       void discover(const Arc& edge) {
  1426         _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
  1427       }
  1428       void examine(const Arc& edge) {
  1429         _bipartite = _bipartite &&
  1430           _part[_graph.target(edge)] != _part[_graph.source(edge)];
  1431       }
  1432 
  1433     private:
  1434 
  1435       const Digraph& _graph;
  1436       PartMap& _part;
  1437       bool& _bipartite;
  1438     };
  1439   }
  1440 
  1441   /// \ingroup connectivity
  1442   ///
  1443   /// \brief Check if the given undirected graph is bipartite or not
  1444   ///
  1445   /// The function checks if the given undirected \c graph graph is bipartite
  1446   /// or not. The \ref Bfs algorithm is used to calculate the result.
  1447   /// \param graph The undirected graph.
  1448   /// \return %True if \c graph is bipartite, %false otherwise.
  1449   /// \sa bipartitePartitions
  1450   template<typename Graph>
  1451   inline bool bipartite(const Graph &graph){
  1452     using namespace _topology_bits;
  1453 
  1454     checkConcept<concepts::Graph, Graph>();
  1455 
  1456     typedef typename Graph::NodeIt NodeIt;
  1457     typedef typename Graph::ArcIt ArcIt;
  1458 
  1459     bool bipartite = true;
  1460 
  1461     BipartiteVisitor<Graph>
  1462       visitor(graph, bipartite);
  1463     BfsVisit<Graph, BipartiteVisitor<Graph> >
  1464       bfs(graph, visitor);
  1465     bfs.init();
  1466     for(NodeIt it(graph); it != INVALID; ++it) {
  1467       if(!bfs.reached(it)){
  1468         bfs.addSource(it);
  1469         while (!bfs.emptyQueue()) {
  1470           bfs.processNextNode();
  1471           if (!bipartite) return false;
  1472         }
  1473       }
  1474     }
  1475     return true;
  1476   }
  1477 
  1478   /// \ingroup connectivity
  1479   ///
  1480   /// \brief Check if the given undirected graph is bipartite or not
  1481   ///
  1482   /// The function checks if the given undirected graph is bipartite
  1483   /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
  1484   /// During the execution, the \c partMap will be set as the two
  1485   /// partitions of the graph.
  1486   /// \param graph The undirected graph.
  1487   /// \retval partMap A writable bool map of nodes. It will be set as the
  1488   /// two partitions of the graph.
  1489   /// \return %True if \c graph is bipartite, %false otherwise.
  1490   template<typename Graph, typename NodeMap>
  1491   inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
  1492     using namespace _topology_bits;
  1493 
  1494     checkConcept<concepts::Graph, Graph>();
  1495 
  1496     typedef typename Graph::Node Node;
  1497     typedef typename Graph::NodeIt NodeIt;
  1498     typedef typename Graph::ArcIt ArcIt;
  1499 
  1500     bool bipartite = true;
  1501 
  1502     BipartitePartitionsVisitor<Graph, NodeMap>
  1503       visitor(graph, partMap, bipartite);
  1504     BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
  1505       bfs(graph, visitor);
  1506     bfs.init();
  1507     for(NodeIt it(graph); it != INVALID; ++it) {
  1508       if(!bfs.reached(it)){
  1509         bfs.addSource(it);
  1510         while (!bfs.emptyQueue()) {
  1511           bfs.processNextNode();
  1512           if (!bipartite) return false;
  1513         }
  1514       }
  1515     }
  1516     return true;
  1517   }
  1518 
  1519   /// \brief Returns true when there are not loop edges in the graph.
  1520   ///
  1521   /// Returns true when there are not loop edges in the graph.
  1522   template <typename Digraph>
  1523   bool loopFree(const Digraph& graph) {
  1524     for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) {
  1525       if (graph.source(it) == graph.target(it)) return false;
  1526     }
  1527     return true;
  1528   }
  1529 
  1530   /// \brief Returns true when there are not parallel edges in the graph.
  1531   ///
  1532   /// Returns true when there are not parallel edges in the graph.
  1533   template <typename Digraph>
  1534   bool parallelFree(const Digraph& graph) {
  1535     typename Digraph::template NodeMap<bool> reached(graph, false);
  1536     for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
  1537       for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1538         if (reached[graph.target(e)]) return false;
  1539         reached.set(graph.target(e), true);
  1540       }
  1541       for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1542         reached.set(graph.target(e), false);
  1543       }
  1544     }
  1545     return true;
  1546   }
  1547 
  1548   /// \brief Returns true when there are not loop edges and parallel
  1549   /// edges in the graph.
  1550   ///
  1551   /// Returns true when there are not loop edges and parallel edges in
  1552   /// the graph.
  1553   template <typename Digraph>
  1554   bool simpleDigraph(const Digraph& graph) {
  1555     typename Digraph::template NodeMap<bool> reached(graph, false);
  1556     for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
  1557       reached.set(n, true);
  1558       for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1559         if (reached[graph.target(e)]) return false;
  1560         reached.set(graph.target(e), true);
  1561       }
  1562       for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1563         reached.set(graph.target(e), false);
  1564       }
  1565       reached.set(n, false);
  1566     }
  1567     return true;
  1568   }
  1569 
  1570 } //namespace lemon
  1571 
  1572 #endif //LEMON_TOPOLOGY_H