/* -*- C++ -*-

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

 *

 * Copyright (C) 2006 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.

  /// \note By definition, the empty graph is connected.

  template <typename UndirGraph>

  bool connected(const UndirGraph& graph) {

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

    typedef typename UndirGraph::NodeIt NodeIt;

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

    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 graph The graph. It should be undirected.

  /// \return The number of components

  /// \note By definition, the empty graph consists

  /// of zero connected 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.

  ///

  /// \image html connected_components.png

  /// \image latex connected_components.eps "Connected components" width=\textwidth

  ///

  /// \param graph The graph. It should be undirected.

  /// \retval compMap 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 paths in both direction.

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

  /// \see connected

  ///

  /// \note By definition, the empty graph is strongly connected.

  template <typename Graph>

  bool stronglyConnected(const Graph& graph) {

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

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

    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 graph The graph.

  /// \return The number of components

  /// \note By definition, the empty graph has zero

  /// strongly connected 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.

  ///

  /// \image html strongly_connected_components.png

  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth

  ///

  /// \param graph The graph.

  /// \retval compMap 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 graph The graph.

  /// \retval cutMap 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 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 CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {

    public:

      typedef typename Graph::Node Node;

      typedef typename Graph::Edge Edge;

      typedef typename Graph::UndirEdge UndirEdge;

      CountBiNodeConnectedComponentsVisitor(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 BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {

    public:

      typedef typename Graph::Node Node;

      typedef typename Graph::Edge Edge;

      typedef typename Graph::UndirEdge UndirEdge;

      BiNodeConnectedComponentsVisitor(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 BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {

    public:

      typedef typename Graph::Node Node;

      typedef typename Graph::Edge Edge;

      typedef typename Graph::UndirEdge UndirEdge;

      BiNodeConnectedCutNodesVisitor(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 countBiNodeConnectedComponents(const UndirGraph& graph);

  /// \ingroup topology

  ///

  /// \brief Checks the graph is bi-node-connected.

  ///

  /// This function checks that the undirected graph is bi-node-connected  

  /// graph. The graph is bi-node-connected if any two undirected edge is 

  /// on same circle.

  ///

  /// \param graph The graph.

  /// \return %True when the graph bi-node-connected.

  /// \todo Make it faster.

  template <typename UndirGraph>

  bool biNodeConnected(const UndirGraph& graph) {

    return countBiNodeConnectedComponents(graph) == 1;

  }

  /// \ingroup topology

  ///

  /// \brief Count the biconnected components.

  ///

  /// This function finds the bi-node-connected 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 countBiNodeConnectedComponents(const UndirGraph& graph) {

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

    typedef typename UndirGraph::NodeIt NodeIt;

    using namespace _topology_bits;

    typedef CountBiNodeConnectedComponentsVisitor<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 bi-node-connected components.

  ///

  /// This function finds the bi-node-connected components in an undirected 

  /// graph. The bi-node-connected components are the classes of an equivalence

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

  /// when they are on same circle.

  ///

  /// \image html node_biconnected_components.png

  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth

  ///

  /// \param graph The graph.

  /// \retval compMap 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 biNodeConnectedComponents(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 BiNodeConnectedComponentsVisitor<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 bi-node-connected cut nodes.

  ///

  /// This function finds the bi-node-connected cut nodes in an undirected 

  /// graph. The bi-node-connected 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 cutMap 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 biNodeConnectedCutNodes(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 BiNodeConnectedCutNodesVisitor<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 CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {

    public:

      typedef typename Graph::Node Node;

      typedef typename Graph::Edge Edge;

      typedef typename Graph::UndirEdge UndirEdge;

      CountBiEdgeConnectedComponentsVisitor(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 BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {

    public:

      typedef typename Graph::Node Node;

      typedef typename Graph::Edge Edge;

      typedef typename Graph::UndirEdge UndirEdge;

      BiEdgeConnectedComponentsVisitor(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 BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {

    public:

      typedef typename Graph::Node Node;

      typedef typename Graph::Edge Edge;

      typedef typename Graph::UndirEdge UndirEdge;

      BiEdgeConnectedCutEdgesVisitor(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;

	  }

	}	

      }