source: lemon-0.x/lemon/topology.h @ 2110:4b8153513f34

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-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/ugraph.h>
#include <lemon/concept_check.h>

#include <lemon/bin_heap.h>
#include <lemon/bucket_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 UGraph>
  bool connected(const UGraph& graph) {
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::NodeIt NodeIt;
    if (NodeIt(graph) == INVALID) return true;
    Dfs<UGraph> 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 UGraph>
  int countConnectedComponents(const UGraph &graph) {
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::Node Node;
    typedef typename UGraph::Edge Edge;

    typedef NullMap<Node, Edge> PredMap;
    typedef NullMap<Node, int> DistMap;

    int compNum = 0;
    typename Bfs<UGraph>::
      template DefPredMap<PredMap>::
      template DefDistMap<DistMap>::
      Create bfs(graph);

    PredMap predMap;
    bfs.predMap(predMap);

    DistMap distMap;
    bfs.distMap(distMap);

    bfs.init();
    for(typename UGraph::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 UGraph, class NodeMap>
  int connectedComponents(const UGraph &graph, NodeMap &compMap) {
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::Node Node;
    typedef typename UGraph::Edge Edge;
    checkConcept<concept::WriteMap<Node, int>, NodeMap>();

    typedef NullMap<Node, Edge> PredMap;
    typedef NullMap<Node, int> DistMap;

    int compNum = 0;
    typename Bfs<UGraph>::
      template DefPredMap<PredMap>::
      template DefDistMap<DistMap>::
      Create bfs(graph);

    PredMap predMap;
    bfs.predMap(predMap);

    DistMap distMap;
    bfs.distMap(distMap);
    
    bfs.init();
    for(typename UGraph::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>();

    typedef typename Graph::Node Node;
    typedef typename Graph::NodeIt NodeIt;

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

    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::UEdge UEdge;

      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::UEdge UEdge;

      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<UEdge> _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::UEdge UEdge;

      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<UEdge> _edgeStack;
      int _num;
      bool rootCut;
    };

  }

  template <typename UGraph>
  int countBiNodeConnectedComponents(const UGraph& 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 UGraph>
  bool biNodeConnected(const UGraph& 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 UGraph>
  int countBiNodeConnectedComponents(const UGraph& graph) {
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::NodeIt NodeIt;

    using namespace _topology_bits;

    typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor;

    int compNum = 0;
    Visitor visitor(graph, compNum);

    DfsVisit<UGraph, 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 uedge 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 UGraph, typename UEdgeMap>
  int biNodeConnectedComponents(const UGraph& graph, 
                                UEdgeMap& compMap) {
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::NodeIt NodeIt;
    typedef typename UGraph::UEdge UEdge;
    checkConcept<concept::WriteMap<UEdge, int>, UEdgeMap>();

    using namespace _topology_bits;

    typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor;
    
    int compNum = 0;
    Visitor visitor(graph, compMap, compNum);

    DfsVisit<UGraph, 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 UGraph, typename NodeMap>
  int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) {
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::Node Node;
    typedef typename UGraph::NodeIt NodeIt;
    checkConcept<concept::WriteMap<Node, bool>, NodeMap>();

    using namespace _topology_bits;

    typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor;
    
    int cutNum = 0;
    Visitor visitor(graph, cutMap, cutNum);

    DfsVisit<UGraph, 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::UEdge UEdge;

      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::UEdge UEdge;

      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::UEdge UEdge;

      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;
          }
        }       
      }

      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 UGraph>
  int countbiEdgeConnectedComponents(const UGraph& graph);

  /// \ingroup topology
  ///
  /// \brief Checks that the graph is bi-edge-connected.
  ///
  /// This function checks that the graph is bi-edge-connected. The undirected
  /// graph is bi-edge-connected 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 UGraph>
  bool biEdgeConnected(const UGraph& graph) { 
    return countBiEdgeConnectedComponents(graph) == 1;
  }

  /// \ingroup topology
  ///
  /// \brief Count the bi-edge-connected components.
  ///
  /// This function count the bi-edge-connected components in an undirected 
  /// graph. The bi-edge-connected 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 UGraph>
  int countBiEdgeConnectedComponents(const UGraph& graph) { 
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::NodeIt NodeIt;

    using namespace _topology_bits;

    typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor;
    
    int compNum = 0;
    Visitor visitor(graph, compNum);

    DfsVisit<UGraph, 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-edge-connected components.
  ///
  /// This function finds the bi-edge-connected components in an undirected 
  /// graph. The bi-edge-connected 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.
  ///
  /// \image html edge_biconnected_components.png
  /// \image latex edge_biconnected_components.eps "bi-edge-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 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 UGraph, typename NodeMap>
  int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) { 
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::NodeIt NodeIt;
    typedef typename UGraph::Node Node;
    checkConcept<concept::WriteMap<Node, int>, NodeMap>();

    using namespace _topology_bits;

    typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor;
    
    int compNum = 0;
    Visitor visitor(graph, compMap, compNum);

    DfsVisit<UGraph, 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-edge-connected cut edges.
  ///
  /// This function finds the bi-edge-connected components in an undirected 
  /// graph. The bi-edge-connected 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 bi-edge-connected 
  /// components are separted by edges which are the cut edges of the 
  /// components.
  ///
  /// \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 UGraph, typename UEdgeMap>
  int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) { 
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::NodeIt NodeIt;
    typedef typename UGraph::UEdge UEdge;
    checkConcept<concept::WriteMap<UEdge, bool>, UEdgeMap>();

    using namespace _topology_bits;

    typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor;
    
    int cutNum = 0;
    Visitor visitor(graph, cutMap, cutNum);

    DfsVisit<UGraph, 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 graph The graph. It should be directed and acyclic.
  /// \retval order 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 graph The graph. It should 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 UGraph>
  bool acyclic(const UGraph& graph) {
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::Node Node;
    typedef typename UGraph::NodeIt NodeIt;
    typedef typename UGraph::Edge Edge;
    Dfs<UGraph> 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.predEdge(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 UGraph>
  bool tree(const UGraph& graph) {
    checkConcept<concept::UGraph, UGraph>();
    typedef typename UGraph::Node Node;
    typedef typename UGraph::NodeIt NodeIt;
    typedef typename UGraph::Edge Edge;
    Dfs<UGraph> 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.predEdge(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 if the given undirected graph is bipartite or not
  ///
  /// The function checks if the given undirected \c graph graph is bipartite 
  /// or not. The \ref Bfs algorithm is used to calculate the result.
  /// \param graph The undirected graph.
  /// \return %True if \c graph is bipartite, %false otherwise.
  /// \sa bipartitePartitions
  ///
  /// \author Balazs Attila Mihaly  
  template<typename UGraph>
  inline bool bipartite(const UGraph &graph){
    checkConcept<concept::UGraph, UGraph>();
    
    typedef typename UGraph::NodeIt NodeIt;
    typedef typename UGraph::EdgeIt EdgeIt;
    
    Bfs<UGraph> bfs(graph);
    bfs.init();
    for(NodeIt i(graph);i!=INVALID;++i){
      if(!bfs.reached(i)){
        bfs.run(i);
      }
    }
    for(EdgeIt i(graph);i!=INVALID;++i){
      if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
    }
    return true;
  }
  
  /// \ingroup topology
  ///
  /// \brief Check if the given undirected graph is bipartite or not
  ///
  /// The function checks if the given undirected graph is bipartite 
  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result. 
  /// During the execution, the \c partMap will be set as the two 
  /// partitions of the graph.
  /// \param graph The undirected graph.
  /// \retval partMap A writable bool map of nodes. It will be set as the
  /// two partitions of the graph. 
  /// \return %True if \c graph is bipartite, %false otherwise.
  ///
  /// \author Balazs Attila Mihaly  
  ///
  /// \image html bipartite_partitions.png
  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
  template<typename UGraph, typename NodeMap>
  inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
    checkConcept<concept::UGraph, UGraph>();
    
    typedef typename UGraph::Node Node;
    typedef typename UGraph::NodeIt NodeIt;
    typedef typename UGraph::EdgeIt EdgeIt;
  
    Bfs<UGraph> bfs(graph);
    bfs.init();
    for(NodeIt i(graph);i!=INVALID;++i){
      if(!bfs.reached(i)){
        bfs.addSource(i);
        for(Node j=bfs.processNextNode();!bfs.emptyQueue();
            j=bfs.processNextNode()){
          partMap.set(j,bfs.dist(j)%2==0);
        }
      }
    }
    for(EdgeIt i(graph);i!=INVALID;++i){
      if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
    }
    return true;
  }
   
} //namespace lemon

#endif //LEMON_TOPOLOGY_H