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