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