# HG changeset patch
# User deba
# Date 1130945026 0
# Node ID 5c76ebbb48187483e4ac8a21c53126592cbbf612
# Parent  c13f6b4aa40e4cf465974c175e17bf555f8955ba
Connected components, etc...
Based on the dfs visitor interface

diff -r c13f6b4aa40e -r 5c76ebbb4818 doc/groups.dox
--- a/doc/groups.dox	Wed Nov 02 15:22:28 2005 +0000
+++ b/doc/groups.dox	Wed Nov 02 15:23:46 2005 +0000
@@ -125,6 +125,13 @@
 */
 
 /**
+@defgroup topology Topology related algorithms
+@ingroup galgs
+\brief This group describes the algorithms
+for discover the topology of the graphs.
+*/
+
+/**
 @defgroup exceptions Exceptions
 This group contains the exceptions thrown by LEMON library
 */
diff -r c13f6b4aa40e -r 5c76ebbb4818 lemon/topology.h
--- a/lemon/topology.h	Wed Nov 02 15:22:28 2005 +0000
+++ b/lemon/topology.h	Wed Nov 02 15:23:46 2005 +0000
@@ -20,49 +20,1208 @@
 #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>
 
-/// \ingroup flowalgs
+#include <lemon/bin_heap.h>
+#include <lemon/linear_heap.h>
+
+#include <stack>
+#include <functional>
+
+/// \ingroup topology
 /// \file
 /// \brief Topology related algorithms
 ///
 /// Topology related algorithms
-///\todo Place the file contents is the module tree.
 
 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 NodeMap>
-    class BackCounterMap {
+    template <typename Graph>
+    class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
     public:
-      BackCounterMap(NodeMap& _nodeMap, int _counter)
-	: nodeMap(_nodeMap), counter(_counter) {}
+      typedef typename Graph::Node Node;
+      typedef typename Graph::Edge Edge;
+      typedef typename Graph::UndirEdge UndirEdge;
 
-      void set(typename NodeMap::Key key, bool val) {
-	if (val) {
-	  nodeMap.set(key, --counter);
-	} else {
-	  nodeMap.set(key, -1);
+      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)]);
 	}
       }
 
-      bool operator[](typename NodeMap::Key key) const {
-	return nodeMap[key] != -1;
+      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:
-      NodeMap& nodeMap;
-      int counter;
+      IntNodeMap& _order;
+      int _num;
     };
+    
   }
 
-  // \todo Its to special output // ReadWriteMap
+  /// \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>
-  bool topological_sort(const Graph& graph, NodeMap& 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>();
@@ -72,35 +1231,39 @@
     typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::Edge Edge;
 
-    typedef BackCounterMap<NodeMap> ProcessedMap;
+    order = constMap<Node, int, -1>();
 
-    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
-      Create dfs(graph);
+    TopologicalSortVisitor<Graph, NodeMap> 
+      visitor(order, countNodes(graph)); 
 
-    ProcessedMap processed(nodeMap, countNodes(graph));
+    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
+      dfs(graph, visitor);
 
-    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();
-	}
+ 	  Edge edge = dfs.nextEdge();
+ 	  Node target = graph.target(edge);
+ 	  if (dfs.reached(target) && order[target] == -1) {
+ 	    return false;
+ 	  }
+ 	  dfs.processNextEdge();
+ 	}
       }
-    }    
+    }
     return true;
   }
 
-  /// \brief Check that the given graph is a DAG.
+  /// \ingroup topology
   ///
-  /// Check that the given graph is a DAG. The DAG is
+  /// \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) {
 
@@ -135,29 +1298,14 @@
     return true;
   }
 
-  // UndirGraph algorithms
-
-  /// \brief Check that the given undirected graph is connected.
+  /// \ingroup topology
   ///
-  /// Check that the given undirected graph 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;
-  }
-
   /// \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>();
@@ -184,16 +1332,19 @@
     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;
-    if (NodeIt(graph) == INVALID) return false;
     Dfs<UndirGraph> dfs(graph);
     dfs.init();
     dfs.addSource(NodeIt(graph));
@@ -214,208 +1365,45 @@
     }    
     return true;
   }
- 
-  ///Count the number of connected components of an undirected graph
 
-  ///Count the number of connected components of an undirected graph
+  /// \ingroup topology
   ///
-  ///\param g The graph. In must be undirected.
-  ///\return The number of components
-  template <class UndirGraph>
-  int countConnectedComponents(const UndirGraph &g) {
+  /// \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>();
-    int c = 0;
-    Bfs<UndirGraph> bfs(g);
-    bfs.init();
-    for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
-      if(!bfs.reached(n)) {
-	bfs.addSource(n);
-	bfs.start();
-	++c;
-      }
-    }
-    return c;
-  }
-
-
-  ///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
-  ///\todo Test required
-  template <class UndirGraph, class IntNodeMap>
-  int connectedComponents(const UndirGraph &g, IntNodeMap &comp) {
-    checkConcept<concept::UndirGraph, UndirGraph>();
-    checkConcept<concept::WriteMap<typename UndirGraph::Node, int>, 
-      IntNodeMap>();
-    int c = 0;
-    Bfs<UndirGraph> bfs(g);
-    bfs.init();
-    for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
-      if(!bfs.reached(n)) {
-	bfs.addSource(n);
-	while (!bfs.emptyQueue()) {
-	  comp[bfs.nextNode()] = c;
-	  bfs.processNextNode();
-	}
-	++c;
-      }
-    }
-    return c;
-  }
-
-  namespace _components_bits {
-
-    template <typename Key, typename IntMap>
-    struct FillWriteMap : public MapBase<Key, bool> {
-    public:
-      FillWriteMap(IntMap& _map, int& _comp) 
-	: map(_map), comp(_comp) {}
-      void set(Key key, bool value) {
-	if (value) { map.set(key, comp); }
-      }
-    private:
-      IntMap& map;
-      int& comp;
-    };
-
-    template <typename Key, typename Container = std::vector<Key> >
-    struct BackInserterWriteMap : public MapBase<Key, bool> {
-    public:
-      BackInserterWriteMap(Container& _container) 
-	: container(_container) {}
-      void set(Key key, bool value) {
-	if (value) { container.push_back(key); }
-      }
-    private:
-      Container& container;
-    };
-
-  }
-
-  /// \brief Count the strongly connected components of a directed graph
-  ///
-  /// Count the strongly connected components of a directed graph
-  ///
-  /// \param g The graph.
-  /// \return The number of components
-  template <typename Graph>
-  int countStronglyConnectedComponents(const Graph& graph) {
-    checkConcept<concept::StaticGraph, Graph>();
-
-    using namespace _components_bits;
-
-    typedef typename Graph::Node Node;
-    typedef typename Graph::Edge Edge;
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-    
-
-    typename Dfs<Graph>::
-      template DefProcessedMap<BackInserterWriteMap<Node> >::
-      Create dfs(graph);
-
-    std::vector<Node> nodes;
-    BackInserterWriteMap<Node> processed(nodes);
-    dfs.processedMap(processed);
-
+    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);
-	dfs.start();
+	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();
+	}
       }
     }
-
-    typedef RevGraphAdaptor<const Graph> RGraph;
-
-    RGraph rgraph(graph);
-
-    Dfs<RGraph> rdfs(rgraph);
-
-    int num = 0;
-
-    rdfs.init();
-    for (typename std::vector<Node>::reverse_iterator 
-	   it = nodes.rbegin(); it != nodes.rend(); ++it) {
-      if (!rdfs.reached(*it)) {
-	rdfs.addSource(*it);
-	rdfs.start();
-	++num;
-      }
-    }
-    return num;
+    return true;
   }
-
-  /// \brief Find the strongly connected components of a directed graph
-  ///
-  /// Find the strongly connected components of a directed graph
-  ///
-  /// \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 IntNodeMap>
-  int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) {
-    checkConcept<concept::StaticGraph, Graph>();
-    checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>();
-
-    using namespace _components_bits;
-
-    typedef typename Graph::Node Node;
-    typedef typename Graph::Edge Edge;
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-    
-
-    typename Dfs<Graph>::
-      template DefProcessedMap<BackInserterWriteMap<Node> >::
-      Create dfs(graph);
-
-    std::vector<Node> nodes;
-    BackInserterWriteMap<Node> processed(nodes);
-    dfs.processedMap(processed);
-
-    dfs.init();
-    for (NodeIt it(graph); it != INVALID; ++it) {
-      if (!dfs.reached(it)) {
-	dfs.addSource(it);
-	dfs.start();
-      }
-    }
-
-    typedef RevGraphAdaptor<const Graph> RGraph;
-
-    RGraph rgraph(graph);
-
-    typename Dfs<RGraph>::
-      template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >::
-      Create rdfs(rgraph);
-
-    int num = 0;
-    FillWriteMap<Node, IntNodeMap> rprocessed(comp, num);
-    rdfs.processedMap(rprocessed);
-
-    rdfs.init();
-    for (typename std::vector<Node>::reverse_iterator 
-	   it = nodes.rbegin(); it != nodes.rend(); ++it) {
-      if (!rdfs.reached(*it)) {
-	rdfs.addSource(*it);
-	rdfs.start();
-	++num;
-      }
-    }
-    return num;
-  }
-
+   
 } //namespace lemon
 
 #endif //LEMON_TOPOLOGY_H