lemon/connectivity.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 425 cace3206223b
child 559 c5fd2d996909
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

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