/* -*- C++ -*-

  * lemon/topology.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_TOPOLOGY_H

 #define LEMON_TOPOLOGY_H

 #include <lemon/dfs.h>

 #include <lemon/bfs.h>

 #include <lemon/graph_utils.h>

 #include <lemon/graph_adaptor.h>

 #include <lemon/maps.h>

 #include <lemon/concept/graph.h>

 #include <lemon/concept/undir_graph.h>

 #include <lemon/concept_check.h>

 #include <lemon/bin_heap.h>

 #include <lemon/linear_heap.h>

 #include <stack>

 #include <functional>

 /// \ingroup topology

 /// \file

 /// \brief Topology related algorithms

 ///

 /// Topology related algorithms

 namespace lemon {

   /// \ingroup topology

   ///

   /// \brief Check that the given undirected graph is connected.

   ///

   /// Check that the given undirected graph connected.

   /// \param graph The undirected graph.

   /// \return %True when there is path between any two nodes in the graph.

   /// \warning The empty graph is not connected.

   template <typename UndirGraph>

   bool connected(const UndirGraph& graph) {

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::NodeIt NodeIt;

     if (NodeIt(graph) == INVALID) return false;

     Dfs<UndirGraph> dfs(graph);

     dfs.run(NodeIt(graph));

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	return false;

       }

     }

     return true;

   }

   /// \ingroup topology

   ///

   /// \brief Count the number of connected components of an undirected graph

   ///

   /// Count the number of connected components of an undirected graph

   ///

   /// \param g The graph. In must be undirected.

   /// \return The number of components

   template <typename UndirGraph>

   int countConnectedComponents(const UndirGraph &graph) {

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::Node Node;

     typedef typename UndirGraph::Edge Edge;

     typedef NullMap<Node, Edge> PredMap;

     typedef NullMap<Node, int> DistMap;

     int compNum = 0;

     typename Bfs<UndirGraph>::

       template DefPredMap<PredMap>::

       template DefDistMap<DistMap>::

       Create bfs(graph);

     PredMap predMap;

     bfs.predMap(predMap);

     DistMap distMap;

     bfs.distMap(distMap);

     bfs.init();

     for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {

       if (!bfs.reached(n)) {

 	bfs.addSource(n);

 	bfs.start();

 	++compNum;

       }

     }

     return compNum;

   }

   /// \ingroup topology

   ///

   /// \brief Find the connected components of an undirected graph

   ///

   /// Find the connected components of an undirected graph.

   ///

   /// \param g The graph. In must be undirected.

   /// \retval comp A writable node map. The values will be set from 0 to

   /// the number of the connected components minus one. Each values of the map

   /// will be set exactly once, the values of a certain component will be

   /// set continuously.

   /// \return The number of components

   template <class UndirGraph, class NodeMap>

   int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::Node Node;

     typedef typename UndirGraph::Edge Edge;

     checkConcept<concept::WriteMap<Node, int>, NodeMap>();

     typedef NullMap<Node, Edge> PredMap;

     typedef NullMap<Node, int> DistMap;

     int compNum = 0;

     typename Bfs<UndirGraph>::

       template DefPredMap<PredMap>::

       template DefDistMap<DistMap>::

       Create bfs(graph);

     PredMap predMap;

     bfs.predMap(predMap);

     DistMap distMap;

     bfs.distMap(distMap);

     bfs.init();

     for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {

       if(!bfs.reached(n)) {

 	bfs.addSource(n);

 	while (!bfs.emptyQueue()) {

 	  compMap.set(bfs.nextNode(), compNum);

 	  bfs.processNextNode();

 	}

 	++compNum;

       }

     }

     return compNum;

   }

   namespace _topology_bits {

     template <typename Graph, typename Iterator >

     struct LeaveOrderVisitor : public DfsVisitor<Graph> {

     public:

       typedef typename Graph::Node Node;

       LeaveOrderVisitor(Iterator it) : _it(it) {}

       void leave(const Node& node) {

 	*(_it++) = node;

       }

     private:

       Iterator _it;

     };

     template <typename Graph, typename Map>

     struct FillMapVisitor : public DfsVisitor<Graph> {

     public:

       typedef typename Graph::Node Node;

       typedef typename Map::Value Value;

       FillMapVisitor(Map& map, Value& value) 

 	: _map(map), _value(value) {}

       void reach(const Node& node) {

 	_map.set(node, _value);

       }

     private:

       Map& _map;

       Value& _value;

     };

     template <typename Graph, typename EdgeMap>

     struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Graph> {

     public:

       typedef typename Graph::Node Node;

       typedef typename Graph::Edge Edge;

       StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap, 

 				       int& cutNum) 

 	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 

 	  _compMap(graph), _num(0) {

       }

       void stop(const Node&) {

 	++_num;

       }

       void reach(const Node& node) {

 	_compMap.set(node, _num);

       }

       void examine(const Edge& edge) {

  	if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) {

  	  _cutMap.set(edge, true);

  	  ++_cutNum;

  	}

       }

     private:

       const Graph& _graph;

       EdgeMap& _cutMap;

       int& _cutNum;

       typename Graph::template NodeMap<int> _compMap;

       int _num;

     };

   }

   /// \ingroup topology

   ///

   /// \brief Check that the given directed graph is strongly connected.

   ///

   /// Check that the given directed graph is strongly connected. The

   /// graph is strongly connected when any two nodes of the graph are

   /// connected with directed pathes in both direction.

   /// \return %False when the graph is not strongly connected.

   /// \see connected

   ///

   /// \waning Empty graph is not strongly connected.

   template <typename Graph>

   bool stronglyConnected(const Graph& graph) {

     checkConcept<concept::StaticGraph, Graph>();

     if (NodeIt(graph) == INVALID) return false;

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

     using namespace _topology_bits;

     typedef DfsVisitor<Graph> Visitor;

     Visitor visitor;

     DfsVisit<Graph, Visitor> dfs(graph, visitor);

     dfs.init();

     dfs.addSource(NodeIt(graph));

     dfs.start();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	return false;

       }

     }

     typedef RevGraphAdaptor<const Graph> RGraph;

     RGraph rgraph(graph);

     typedef DfsVisitor<Graph> RVisitor;

     RVisitor rvisitor;

     DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);

     rdfs.init();    

     rdfs.addSource(NodeIt(graph));

     rdfs.start();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!rdfs.reached(it)) {

 	return false;

       }

     }

     return true;

   }

   /// \ingroup topology

   ///

   /// \brief Count the strongly connected components of a directed graph

   ///

   /// Count the strongly connected components of a directed graph.

   /// The strongly connected components are the classes of an equivalence

   /// relation on the nodes of the graph. Two nodes are connected with

   /// directed paths in both direction.

   ///

   /// \param g The graph.

   /// \return The number of components

   template <typename Graph>

   int countStronglyConnectedComponents(const Graph& graph) {

     checkConcept<concept::StaticGraph, Graph>();

     using namespace _topology_bits;

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::EdgeIt EdgeIt;

     typedef std::vector<Node> Container;

     typedef typename Container::iterator Iterator;

     Container nodes(countNodes(graph));

     typedef LeaveOrderVisitor<Graph, Iterator> Visitor;

     Visitor visitor(nodes.begin());

     DfsVisit<Graph, Visitor> dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	dfs.start();

       }

     }

     typedef typename Container::reverse_iterator RIterator;

     typedef RevGraphAdaptor<const Graph> RGraph;

     RGraph rgraph(graph);

     typedef DfsVisitor<Graph> RVisitor;

     RVisitor rvisitor;

     DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);

     int compNum = 0;

     rdfs.init();

     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {

       if (!rdfs.reached(*it)) {

 	rdfs.addSource(*it);

 	rdfs.start();

 	++compNum;

       }

     }

     return compNum;

   }

   /// \ingroup topology

   ///

   /// \brief Find the strongly connected components of a directed graph

   ///

   /// Find the strongly connected components of a directed graph.

   /// The strongly connected components are the classes of an equivalence

   /// relation on the nodes of the graph. Two nodes are in relationship

   /// when there are directed paths between them in both direction.

   ///

   /// \param g The graph.

   /// \retval comp A writable node map. The values will be set from 0 to

   /// the number of the strongly connected components minus one. Each values 

   /// of the map will be set exactly once, the values of a certain component 

   /// will be set continuously.

   /// \return The number of components

   template <typename Graph, typename NodeMap>

   int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {

     checkConcept<concept::StaticGraph, Graph>();

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

     checkConcept<concept::WriteMap<Node, int>, NodeMap>();

     using namespace _topology_bits;

     typedef std::vector<Node> Container;

     typedef typename Container::iterator Iterator;

     Container nodes(countNodes(graph));

     typedef LeaveOrderVisitor<Graph, Iterator> Visitor;

     Visitor visitor(nodes.begin());

     DfsVisit<Graph, Visitor> dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	dfs.start();

       }

     }

     typedef typename Container::reverse_iterator RIterator;

     typedef RevGraphAdaptor<const Graph> RGraph;

     RGraph rgraph(graph);

     int compNum = 0;

     typedef FillMapVisitor<RGraph, NodeMap> RVisitor;

     RVisitor rvisitor(compMap, compNum);

     DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);

     rdfs.init();

     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {

       if (!rdfs.reached(*it)) {

 	rdfs.addSource(*it);

 	rdfs.start();

 	++compNum;

       }

     }

     return compNum;

   }

   /// \ingroup topology

   ///

   /// \brief Find the cut edges of the strongly connected components.

   ///

   /// Find the cut edges of the strongly connected components.

   /// The strongly connected components are the classes of an equivalence

   /// relation on the nodes of the graph. Two nodes are in relationship

   /// when there are directed paths between them in both direction.

   /// The strongly connected components are separated by the cut edges.

   ///

   /// \param g The graph.

   /// \retval comp A writable edge map. The values will be set true when

   /// the edge is cut edge otherwise false.

   ///

   /// \return The number of cut edges

   template <typename Graph, typename EdgeMap>

   int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {

     checkConcept<concept::StaticGraph, Graph>();

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::NodeIt NodeIt;

     checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>();

     using namespace _topology_bits;

     typedef std::vector<Node> Container;

     typedef typename Container::iterator Iterator;

     Container nodes(countNodes(graph));

     typedef LeaveOrderVisitor<Graph, Iterator> Visitor;

     Visitor visitor(nodes.begin());

     DfsVisit<Graph, Visitor> dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	dfs.start();

       }

     }

     typedef typename Container::reverse_iterator RIterator;

     typedef RevGraphAdaptor<const Graph> RGraph;

     RGraph rgraph(graph);

     int cutNum = 0;

     typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;

     RVisitor rvisitor(rgraph, cutMap, cutNum);

     DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);

     rdfs.init();

     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {

       if (!rdfs.reached(*it)) {

 	rdfs.addSource(*it);

 	rdfs.start();

       }

     }

     return cutNum;

   }

   namespace _topology_bits {

     template <typename Graph>

     class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {

     public:

       typedef typename Graph::Node Node;

       typedef typename Graph::Edge Edge;

       typedef typename Graph::UndirEdge UndirEdge;

       CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) 

 	: _graph(graph), _compNum(compNum), 

 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}

       void start(const Node& node) {

 	_predMap.set(node, INVALID);

       }

       void reach(const Node& node) {

 	_numMap.set(node, _num);

 	_retMap.set(node, _num);

 	++_num;

       }

       void discover(const Edge& edge) {

 	_predMap.set(_graph.target(edge), _graph.source(edge));

       }

       void examine(const Edge& edge) {

 	if (_graph.source(edge) == _graph.target(edge) && 

 	    _graph.direction(edge)) {

 	  ++_compNum;

 	  return;

 	}

 	if (_predMap[_graph.source(edge)] == _graph.target(edge)) {

 	  return;

 	}

 	if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {

 	  _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);

 	}

       }

       void backtrack(const Edge& edge) {

 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {

 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);

 	}  

 	if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {

 	  ++_compNum;

 	}

       }

     private:

       const Graph& _graph;

       int& _compNum; 

       typename Graph::template NodeMap<int> _numMap;

       typename Graph::template NodeMap<int> _retMap;

       typename Graph::template NodeMap<Node> _predMap;

       int _num;

     };

     template <typename Graph, typename EdgeMap>

     class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {

     public:

       typedef typename Graph::Node Node;

       typedef typename Graph::Edge Edge;

       typedef typename Graph::UndirEdge UndirEdge;

       NodeBiconnectedComponentsVisitor(const Graph& graph, 

 				       EdgeMap& compMap, int &compNum) 

 	: _graph(graph), _compMap(compMap), _compNum(compNum), 

 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}

       void start(const Node& node) {

 	_predMap.set(node, INVALID);

       }

       void reach(const Node& node) {

 	_numMap.set(node, _num);

 	_retMap.set(node, _num);

 	++_num;

       }

       void discover(const Edge& edge) {

 	Node target = _graph.target(edge);

 	_predMap.set(target, edge);

 	_edgeStack.push(edge);

       }

       void examine(const Edge& edge) {

 	Node source = _graph.source(edge);

 	Node target = _graph.target(edge);

 	if (source == target && _graph.direction(edge)) {

 	  _compMap.set(edge, _compNum);

 	  ++_compNum;

 	  return;

 	}

 	if (_numMap[target] < _numMap[source]) {

 	  if (_predMap[source] != _graph.oppositeEdge(edge)) {

 	    _edgeStack.push(edge);

 	  }

 	}

 	if (_predMap[source] != INVALID && 

 	    target == _graph.source(_predMap[source])) {

 	  return;

 	}

 	if (_retMap[source] > _numMap[target]) {

 	  _retMap.set(source, _numMap[target]);

 	}

       }

       void backtrack(const Edge& edge) {

 	Node source = _graph.source(edge);

 	Node target = _graph.target(edge);

 	if (_retMap[source] > _retMap[target]) {

 	  _retMap.set(source, _retMap[target]);

 	}  

 	if (_numMap[source] <= _retMap[target]) {

 	  while (_edgeStack.top() != edge) {

 	    _compMap.set(_edgeStack.top(), _compNum);

 	    _edgeStack.pop();

 	  }

 	  _compMap.set(edge, _compNum);

 	  _edgeStack.pop();

 	  ++_compNum;

 	}

       }

     private:

       const Graph& _graph;

       EdgeMap& _compMap;

       int& _compNum; 

       typename Graph::template NodeMap<int> _numMap;

       typename Graph::template NodeMap<int> _retMap;

       typename Graph::template NodeMap<Edge> _predMap;

       std::stack<UndirEdge> _edgeStack;

       int _num;

     };

     template <typename Graph, typename NodeMap>

     class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {

     public:

       typedef typename Graph::Node Node;

       typedef typename Graph::Edge Edge;

       typedef typename Graph::UndirEdge UndirEdge;

       NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,

 				     int& cutNum) 

 	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum),

 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}

       void start(const Node& node) {

 	_predMap.set(node, INVALID);

 	rootCut = false;

       }

       void reach(const Node& node) {

 	_numMap.set(node, _num);

 	_retMap.set(node, _num);

 	++_num;

       }

       void discover(const Edge& edge) {

 	_predMap.set(_graph.target(edge), _graph.source(edge));

       }

       void examine(const Edge& edge) {

 	if (_graph.source(edge) == _graph.target(edge) && 

 	    _graph.direction(edge)) {

 	  if (!_cutMap[_graph.source(edge)]) {

 	    _cutMap.set(_graph.source(edge), true);

 	    ++_cutNum;

 	  }

 	  return;

 	}

 	if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;

 	if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {

 	  _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);

 	}

       }

       void backtrack(const Edge& edge) {

 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {

 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);

 	}  

 	if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {

 	  if (_predMap[_graph.source(edge)] != INVALID) {

 	    if (!_cutMap[_graph.source(edge)]) {

 	      _cutMap.set(_graph.source(edge), true);

 	      ++_cutNum;

 	    }

 	  } else if (rootCut) {

 	    if (!_cutMap[_graph.source(edge)]) {

 	      _cutMap.set(_graph.source(edge), true);

 	      ++_cutNum;

 	    }

 	  } else {

 	    rootCut = true;

 	  }

 	}

       }

     private:

       const Graph& _graph;

       NodeMap& _cutMap;

       int& _cutNum; 

       typename Graph::template NodeMap<int> _numMap;

       typename Graph::template NodeMap<int> _retMap;

       typename Graph::template NodeMap<Node> _predMap;

       std::stack<UndirEdge> _edgeStack;

       int _num;

       bool rootCut;

     };

   }

   template <typename UndirGraph>

   int countNodeBiconnectedComponents(const UndirGraph& graph);

   /// \ingroup topology

   ///

   /// \brief Checks the graph is node biconnected.

   ///

   /// This function checks that the undirected graph is node biconnected  

   /// graph. The graph is node biconnected if any two undirected edge is 

   /// on same circle.

   ///

   /// \param graph The graph.

   /// \return %True when the graph node biconnected.

   /// \todo Make it faster.

   template <typename UndirGraph>

   bool nodeBiconnected(const UndirGraph& graph) {

     return countNodeBiconnectedComponents(graph) == 1;

   }

   /// \ingroup topology

   ///

   /// \brief Count the biconnected components.

   ///

   /// This function finds the node biconnected components in an undirected 

   /// graph. The biconnected components are the classes of an equivalence 

   /// relation on the undirected edges. Two undirected edge is in relationship

   /// when they are on same circle.

   ///

   /// \param graph The graph.

   /// \return The number of components.

   template <typename UndirGraph>

   int countNodeBiconnectedComponents(const UndirGraph& graph) {

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::NodeIt NodeIt;

     using namespace _topology_bits;

     typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;

     int compNum = 0;

     Visitor visitor(graph, compNum);

     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	dfs.start();

       }

     }

     return compNum;

   }

   /// \ingroup topology

   ///

   /// \brief Find the node biconnected components.

   ///

   /// This function finds the node biconnected components in an undirected 

   /// graph. The node biconnected components are the classes of an equivalence

   /// relation on the undirected edges. Two undirected edge are in relationship

   /// when they are on same circle.

   ///

   /// \param graph The graph.

   /// \retval comp A writable undir edge map. The values will be set from 0 to

   /// the number of the biconnected components minus one. Each values 

   /// of the map will be set exactly once, the values of a certain component 

   /// will be set continuously.

   /// \return The number of components.

   template <typename UndirGraph, typename UndirEdgeMap>

   int nodeBiconnectedComponents(const UndirGraph& graph, 

 				UndirEdgeMap& compMap) {

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::NodeIt NodeIt;

     typedef typename UndirGraph::UndirEdge UndirEdge;

     checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>();

     using namespace _topology_bits;

     typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;

     int compNum = 0;

     Visitor visitor(graph, compMap, compNum);

     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	dfs.start();

       }

     }

     return compNum;

   }

   /// \ingroup topology

   ///

   /// \brief Find the node biconnected cut nodes.

   ///

   /// This function finds the node biconnected cut nodes in an undirected 

   /// graph. The node biconnected components are the classes of an equivalence

   /// relation on the undirected edges. Two undirected edges are in 

   /// relationship when they are on same circle. The biconnected components 

   /// are separted by nodes which are the cut nodes of the components.

   ///

   /// \param graph The graph.

   /// \retval comp A writable edge map. The values will be set true when

   /// the node separate two or more components.

   /// \return The number of the cut nodes.

   template <typename UndirGraph, typename NodeMap>

   int nodeBiconnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::Node Node;

     typedef typename UndirGraph::NodeIt NodeIt;

     checkConcept<concept::WriteMap<Node, bool>, NodeMap>();

     using namespace _topology_bits;

     typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;

     int cutNum = 0;

     Visitor visitor(graph, cutMap, cutNum);

     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	dfs.start();

       }

     }

     return cutNum;

   }

   namespace _topology_bits {

     template <typename Graph>

     class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {

     public:

       typedef typename Graph::Node Node;

       typedef typename Graph::Edge Edge;

       typedef typename Graph::UndirEdge UndirEdge;

       CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) 

 	: _graph(graph), _compNum(compNum), 

 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}

       void start(const Node& node) {

 	_predMap.set(node, INVALID);

       }

       void reach(const Node& node) {

 	_numMap.set(node, _num);

 	_retMap.set(node, _num);

 	++_num;

       }

       void leave(const Node& node) {

 	if (_numMap[node] <= _retMap[node]) {

 	  ++_compNum;

 	}	

       }

       void discover(const Edge& edge) {

 	_predMap.set(_graph.target(edge), edge);

       }

       void examine(const Edge& edge) {

 	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {

 	  return;

 	}

 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {

 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);

 	}

       }

       void backtrack(const Edge& edge) {

 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {

 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);

 	}  

       }

     private:

       const Graph& _graph;

       int& _compNum; 

       typename Graph::template NodeMap<int> _numMap;

       typename Graph::template NodeMap<int> _retMap;

       typename Graph::template NodeMap<Edge> _predMap;

       int _num;

     };

     template <typename Graph, typename NodeMap>

     class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {

     public:

       typedef typename Graph::Node Node;

       typedef typename Graph::Edge Edge;

       typedef typename Graph::UndirEdge UndirEdge;

       EdgeBiconnectedComponentsVisitor(const Graph& graph, 

 				       NodeMap& compMap, int &compNum) 

 	: _graph(graph), _compMap(compMap), _compNum(compNum), 

 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}

       void start(const Node& node) {

 	_predMap.set(node, INVALID);

       }

       void reach(const Node& node) {

 	_numMap.set(node, _num);

 	_retMap.set(node, _num);

 	_nodeStack.push(node);

 	++_num;

       }

       void leave(const Node& node) {

 	if (_numMap[node] <= _retMap[node]) {

 	  while (_nodeStack.top() != node) {

 	    _compMap.set(_nodeStack.top(), _compNum);

 	    _nodeStack.pop();

 	  }

 	  _compMap.set(node, _compNum);

 	  _nodeStack.pop();

 	  ++_compNum;

 	}	

       }

       void discover(const Edge& edge) {

 	_predMap.set(_graph.target(edge), edge);

       }

       void examine(const Edge& edge) {

 	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {

 	  return;

 	}

 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {

 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);

 	}

       }

       void backtrack(const Edge& edge) {

 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {

 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);

 	}  

       }

     private:

       const Graph& _graph;

       NodeMap& _compMap;

       int& _compNum; 

       typename Graph::template NodeMap<int> _numMap;

       typename Graph::template NodeMap<int> _retMap;

       typename Graph::template NodeMap<Edge> _predMap;

       std::stack<Node> _nodeStack;

       int _num;

     };

     template <typename Graph, typename EdgeMap>

     class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {

     public:

       typedef typename Graph::Node Node;

       typedef typename Graph::Edge Edge;

       typedef typename Graph::UndirEdge UndirEdge;

       EdgeBiconnectedCutEdgesVisitor(const Graph& graph, 

 				     EdgeMap& cutMap, int &cutNum) 

 	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 

 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}

       void start(const Node& node) {

 	_predMap[node] = INVALID;

       }

       void reach(const Node& node) {

 	_numMap.set(node, _num);

 	_retMap.set(node, _num);

 	++_num;

       }

       void leave(const Node& node) {

 	if (_numMap[node] <= _retMap[node]) {

 	  if (_predMap[node] != INVALID) {

 	    _cutMap.set(_predMap[node], true);

 	    ++_cutNum;

 	  }

 	}	

       }

       void discover(const Edge& edge) {

 	_predMap.set(_graph.target(edge), edge);

       }

       void examine(const Edge& edge) {

 	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {

 	  return;

 	}

 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {

 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);

 	}

       }

       void backtrack(const Edge& edge) {

 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {

 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);

 	}  

       }

     private:

       const Graph& _graph;

       EdgeMap& _cutMap;

       int& _cutNum; 

       typename Graph::template NodeMap<int> _numMap;

       typename Graph::template NodeMap<int> _retMap;

       typename Graph::template NodeMap<Edge> _predMap;

       int _num;

     };

   }

   template <typename UndirGraph>

   int countEdgeBiconnectedComponents(const UndirGraph& graph);

   /// \ingroup topology

   ///

   /// \brief Checks that the graph is edge biconnected.

   ///

   /// This function checks that the graph is edge biconnected. The undirected

   /// graph is edge biconnected when any two nodes are connected with two

   /// edge-disjoint paths.

   ///

   /// \param graph The undirected graph.

   /// \return The number of components.

   /// \todo Make it faster.

   template <typename UndirGraph>

   bool edgeBiconnected(const UndirGraph& graph) { 

     return countEdgeBiconnectedComponents(graph) == 1;

   }

   /// \ingroup topology

   ///

   /// \brief Count the edge biconnected components.

   ///

   /// This function count the edge biconnected components in an undirected 

   /// graph. The edge biconnected components are the classes of an equivalence

   /// relation on the nodes. Two nodes are in relationship when they are  

   /// connected with at least two edge-disjoint paths.

   ///

   /// \param graph The undirected graph.

   /// \return The number of components.

   template <typename UndirGraph>

   int countEdgeBiconnectedComponents(const UndirGraph& graph) { 

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::NodeIt NodeIt;

     using namespace _topology_bits;

     typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;

     int compNum = 0;

     Visitor visitor(graph, compNum);

     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	dfs.start();

       }

     }

     return compNum;

   }

   /// \ingroup topology

   ///

   /// \brief Find the edge biconnected components.

   ///

   /// This function finds the edge biconnected components in an undirected 

   /// graph. The edge biconnected components are the classes of an equivalence

   /// relation on the nodes. Two nodes are in relationship when they are  

   /// connected at least two edge-disjoint paths.

   ///

   /// \param graph The graph.

   /// \retval comp A writable node map. The values will be set from 0 to

   /// the number of the biconnected components minus one. Each values 

   /// of the map will be set exactly once, the values of a certain component 

   /// will be set continuously.

   /// \return The number of components.

   template <typename UndirGraph, typename NodeMap>

   int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) { 

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::NodeIt NodeIt;

     typedef typename UndirGraph::Node Node;

     checkConcept<concept::WriteMap<Node, int>, NodeMap>();

     using namespace _topology_bits;

     typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;

     int compNum = 0;

     Visitor visitor(graph, compMap, compNum);

     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	dfs.start();

       }

     }

     return compNum;

   }

   /// \ingroup topology

   ///

   /// \brief Find the edge biconnected cut edges.

   ///

   /// This function finds the edge biconnected components in an undirected 

   /// graph. The edge biconnected components are the classes of an equivalence

   /// relation on the nodes. Two nodes are in relationship when they are 

   /// connected with at least two edge-disjoint paths. The edge biconnected 

   /// components are separted by edges which are the cut edges of the 

   /// components.

   ///

   /// \param graph The graph.

   /// \retval comp A writable node map. The values will be set true when the

   /// edge is a cut edge.

   /// \return The number of cut edges.

   template <typename UndirGraph, typename UndirEdgeMap>

   int edgeBiconnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { 

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::NodeIt NodeIt;

     typedef typename UndirGraph::UndirEdge UndirEdge;

     checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>();

     using namespace _topology_bits;

     typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;

     int cutNum = 0;

     Visitor visitor(graph, cutMap, cutNum);

     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	dfs.start();

       }

     }

     return cutNum;

   }

   namespace _topology_bits {

     template <typename Graph, typename IntNodeMap>

     class TopologicalSortVisitor : public DfsVisitor<Graph> {

     public:

       typedef typename Graph::Node Node;

       typedef typename Graph::Edge edge;

       TopologicalSortVisitor(IntNodeMap& order, int num) 

 	: _order(order), _num(num) {}

       void leave(const Node& node) {

 	_order.set(node, --_num);

       }

     private:

       IntNodeMap& _order;

       int _num;

     };

   }

   /// \ingroup topology

   ///

   /// \brief Sort the nodes of a DAG into topolgical order.

   ///

   /// Sort the nodes of a DAG into topolgical order.

   ///

   /// \param g The graph. In must be directed and acyclic.

   /// \retval comp A writable node map. The values will be set from 0 to

   /// the number of the nodes in the graph minus one. Each values of the map

   /// will be set exactly once, the values  will be set descending order.

   ///

   /// \see checkedTopologicalSort

   /// \see dag

   template <typename Graph, typename NodeMap>

   void topologicalSort(const Graph& graph, NodeMap& order) {

     using namespace _topology_bits;

     checkConcept<concept::StaticGraph, Graph>();

     checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::Edge Edge;

     TopologicalSortVisitor<Graph, NodeMap> 

       visitor(order, countNodes(graph)); 

     DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >

       dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	dfs.start();

       }

     }    

   }

   /// \ingroup topology

   ///

   /// \brief Sort the nodes of a DAG into topolgical order.

   ///

   /// Sort the nodes of a DAG into topolgical order. It also checks

   /// that the given graph is DAG.

   ///

   /// \param g The graph. In must be directed and acyclic.

   /// \retval order A readable - writable node map. The values will be set 

   /// from 0 to the number of the nodes in the graph minus one. Each values 

   /// of the map will be set exactly once, the values will be set descending 

   /// order.

   /// \return %False when the graph is not DAG.

   ///

   /// \see topologicalSort

   /// \see dag

   template <typename Graph, typename NodeMap>

   bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {

     using namespace _topology_bits;

     checkConcept<concept::StaticGraph, Graph>();

     checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::Edge Edge;

     order = constMap<Node, int, -1>();

     TopologicalSortVisitor<Graph, NodeMap> 

       visitor(order, countNodes(graph)); 

     DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >

       dfs(graph, visitor);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	while (!dfs.emptyQueue()) {

  	  Edge edge = dfs.nextEdge();

  	  Node target = graph.target(edge);

  	  if (dfs.reached(target) && order[target] == -1) {

  	    return false;

  	  }

  	  dfs.processNextEdge();

  	}

       }

     }

     return true;

   }

   /// \ingroup topology

   ///

   /// \brief Check that the given directed graph is a DAG.

   ///

   /// Check that the given directed graph is a DAG. The DAG is

   /// an Directed Acyclic Graph.

   /// \return %False when the graph is not DAG.

   /// \see acyclic

   template <typename Graph>

   bool dag(const Graph& graph) {

     checkConcept<concept::StaticGraph, Graph>();

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::template NodeMap<bool> ProcessedMap;

     typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::

       Create dfs(graph);

     ProcessedMap processed(graph);

     dfs.processedMap(processed);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	while (!dfs.emptyQueue()) {

 	  Edge edge = dfs.nextEdge();

 	  Node target = graph.target(edge);

 	  if (dfs.reached(target) && !processed[target]) {

 	    return false;

 	  }

 	  dfs.processNextEdge();

 	}

       }

     }    

     return true;

   }

   /// \ingroup topology

   ///

   /// \brief Check that the given undirected graph is acyclic.

   ///

   /// Check that the given undirected graph acyclic.

   /// \param graph The undirected graph.

   /// \return %True when there is no circle in the graph.

   /// \see dag

   template <typename UndirGraph>

   bool acyclic(const UndirGraph& graph) {

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::Node Node;

     typedef typename UndirGraph::NodeIt NodeIt;

     typedef typename UndirGraph::Edge Edge;

     Dfs<UndirGraph> dfs(graph);

     dfs.init();

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	while (!dfs.emptyQueue()) {

 	  Edge edge = dfs.nextEdge();

 	  Node source = graph.source(edge);

 	  Node target = graph.target(edge);

 	  if (dfs.reached(target) && 

 	      dfs.pred(source) != graph.oppositeEdge(edge)) {

 	    return false;

 	  }

 	  dfs.processNextEdge();

 	}

       }

     }

     return true;

   }

   /// \ingroup topology

   ///

   /// \brief Check that the given undirected graph is tree.

   ///

   /// Check that the given undirected graph is tree.

   /// \param graph The undirected graph.

   /// \return %True when the graph is acyclic and connected.

   template <typename UndirGraph>

   bool tree(const UndirGraph& graph) {

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::Node Node;

     typedef typename UndirGraph::NodeIt NodeIt;

     typedef typename UndirGraph::Edge Edge;

     Dfs<UndirGraph> dfs(graph);

     dfs.init();

     dfs.addSource(NodeIt(graph));

     while (!dfs.emptyQueue()) {

       Edge edge = dfs.nextEdge();

       Node source = graph.source(edge);

       Node target = graph.target(edge);

       if (dfs.reached(target) && 

 	  dfs.pred(source) != graph.oppositeEdge(edge)) {

 	return false;

       }

       dfs.processNextEdge();

     }

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	return false;

       }

     }    

     return true;

   }

   /// \ingroup topology

   ///

   /// \brief Check that the given undirected graph is bipartite.

   ///

   /// Check that the given undirected graph is bipartite.

   /// \param graph The undirected graph.

   /// \return %True when the nodes can be separated into two sets that

   /// there are not connected nodes in neither sets.

   template <typename UndirGraph>

   bool bipartite(const UndirGraph& graph) {

     checkConcept<concept::UndirGraph, UndirGraph>();

     typedef typename UndirGraph::Node Node;

     typedef typename UndirGraph::NodeIt NodeIt;

     typedef typename UndirGraph::Edge Edge;

     if (NodeIt(graph) == INVALID) return false;

     Dfs<UndirGraph> dfs(graph);

     dfs.init();

     typename UndirGraph::template NodeMap<bool> red(graph);

     for (NodeIt it(graph); it != INVALID; ++it) {

       if (!dfs.reached(it)) {

 	dfs.addSource(it);

 	red[it] = true;

 	while (!dfs.emptyQueue()) {

 	  Edge edge = dfs.nextEdge();

 	  Node source = graph.source(edge);

 	  Node target = graph.target(edge);

 	  if (dfs.reached(target) && red[source] == red[target]) {

 	    return false;

 	  } else {

 	    red[target] = !red[source];

 	  }

 	  dfs.processNextEdge();

 	}

       }

     }

     return true;

   }

 } //namespace lemon

 #endif //LEMON_TOPOLOGY_H