lemon/connectivity.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 04 Mar 2009 14:09:45 +0000
changeset 547 d59dcc933e59
parent 425 cace3206223b
child 559 c5fd2d996909
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 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