Connected components, etc...
authordeba
Wed, 02 Nov 2005 15:23:46 +0000
changeset 17505c76ebbb4818
parent 1749 c13f6b4aa40e
child 1751 a2a454f1232d
Connected components, etc...
Based on the dfs visitor interface
doc/groups.dox
lemon/topology.h
     1.1 --- a/doc/groups.dox	Wed Nov 02 15:22:28 2005 +0000
     1.2 +++ b/doc/groups.dox	Wed Nov 02 15:23:46 2005 +0000
     1.3 @@ -125,6 +125,13 @@
     1.4  */
     1.5  
     1.6  /**
     1.7 +@defgroup topology Topology related algorithms
     1.8 +@ingroup galgs
     1.9 +\brief This group describes the algorithms
    1.10 +for discover the topology of the graphs.
    1.11 +*/
    1.12 +
    1.13 +/**
    1.14  @defgroup exceptions Exceptions
    1.15  This group contains the exceptions thrown by LEMON library
    1.16  */
     2.1 --- a/lemon/topology.h	Wed Nov 02 15:22:28 2005 +0000
     2.2 +++ b/lemon/topology.h	Wed Nov 02 15:23:46 2005 +0000
     2.3 @@ -20,49 +20,1208 @@
     2.4  #include <lemon/dfs.h>
     2.5  #include <lemon/bfs.h>
     2.6  #include <lemon/graph_utils.h>
     2.7 +#include <lemon/graph_adaptor.h>
     2.8 +#include <lemon/maps.h>
     2.9  
    2.10  #include <lemon/concept/graph.h>
    2.11  #include <lemon/concept/undir_graph.h>
    2.12  #include <lemon/concept_check.h>
    2.13  
    2.14 -/// \ingroup flowalgs
    2.15 +#include <lemon/bin_heap.h>
    2.16 +#include <lemon/linear_heap.h>
    2.17 +
    2.18 +#include <stack>
    2.19 +#include <functional>
    2.20 +
    2.21 +/// \ingroup topology
    2.22  /// \file
    2.23  /// \brief Topology related algorithms
    2.24  ///
    2.25  /// Topology related algorithms
    2.26 -///\todo Place the file contents is the module tree.
    2.27  
    2.28  namespace lemon {
    2.29  
    2.30 +  /// \ingroup topology
    2.31 +  ///
    2.32 +  /// \brief Check that the given undirected graph is connected.
    2.33 +  ///
    2.34 +  /// Check that the given undirected graph connected.
    2.35 +  /// \param graph The undirected graph.
    2.36 +  /// \return %True when there is path between any two nodes in the graph.
    2.37 +  /// \warning The empty graph is not connected.
    2.38 +  template <typename UndirGraph>
    2.39 +  bool connected(const UndirGraph& graph) {
    2.40 +    checkConcept<concept::UndirGraph, UndirGraph>();
    2.41 +    typedef typename UndirGraph::NodeIt NodeIt;
    2.42 +    if (NodeIt(graph) == INVALID) return false;
    2.43 +    Dfs<UndirGraph> dfs(graph);
    2.44 +    dfs.run(NodeIt(graph));
    2.45 +    for (NodeIt it(graph); it != INVALID; ++it) {
    2.46 +      if (!dfs.reached(it)) {
    2.47 +	return false;
    2.48 +      }
    2.49 +    }
    2.50 +    return true;
    2.51 +  }
    2.52 +
    2.53 +  /// \ingroup topology
    2.54 +  ///
    2.55 +  /// \brief Count the number of connected components of an undirected graph
    2.56 +  ///
    2.57 +  /// Count the number of connected components of an undirected graph
    2.58 +  ///
    2.59 +  /// \param g The graph. In must be undirected.
    2.60 +  /// \return The number of components
    2.61 +  template <typename UndirGraph>
    2.62 +  int countConnectedComponents(const UndirGraph &graph) {
    2.63 +    checkConcept<concept::UndirGraph, UndirGraph>();
    2.64 +    typedef typename UndirGraph::Node Node;
    2.65 +    typedef typename UndirGraph::Edge Edge;
    2.66 +
    2.67 +    typedef NullMap<Node, Edge> PredMap;
    2.68 +    typedef NullMap<Node, int> DistMap;
    2.69 +
    2.70 +    int compNum = 0;
    2.71 +    typename Bfs<UndirGraph>::
    2.72 +      template DefPredMap<PredMap>::
    2.73 +      template DefDistMap<DistMap>::
    2.74 +      Create bfs(graph);
    2.75 +
    2.76 +    PredMap predMap;
    2.77 +    bfs.predMap(predMap);
    2.78 +
    2.79 +    DistMap distMap;
    2.80 +    bfs.distMap(distMap);
    2.81 +
    2.82 +    bfs.init();
    2.83 +    for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
    2.84 +      if (!bfs.reached(n)) {
    2.85 +	bfs.addSource(n);
    2.86 +	bfs.start();
    2.87 +	++compNum;
    2.88 +      }
    2.89 +    }
    2.90 +    return compNum;
    2.91 +  }
    2.92 +
    2.93 +  /// \ingroup topology
    2.94 +  ///
    2.95 +  /// \brief Find the connected components of an undirected graph
    2.96 +  ///
    2.97 +  /// Find the connected components of an undirected graph.
    2.98 +  ///
    2.99 +  /// \param g The graph. In must be undirected.
   2.100 +  /// \retval comp A writable node map. The values will be set from 0 to
   2.101 +  /// the number of the connected components minus one. Each values of the map
   2.102 +  /// will be set exactly once, the values of a certain component will be
   2.103 +  /// set continuously.
   2.104 +  /// \return The number of components
   2.105 +  template <class UndirGraph, class NodeMap>
   2.106 +  int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {
   2.107 +    checkConcept<concept::UndirGraph, UndirGraph>();
   2.108 +    typedef typename UndirGraph::Node Node;
   2.109 +    typedef typename UndirGraph::Edge Edge;
   2.110 +    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
   2.111 +
   2.112 +    typedef NullMap<Node, Edge> PredMap;
   2.113 +    typedef NullMap<Node, int> DistMap;
   2.114 +
   2.115 +    int compNum = 0;
   2.116 +    typename Bfs<UndirGraph>::
   2.117 +      template DefPredMap<PredMap>::
   2.118 +      template DefDistMap<DistMap>::
   2.119 +      Create bfs(graph);
   2.120 +
   2.121 +    PredMap predMap;
   2.122 +    bfs.predMap(predMap);
   2.123 +
   2.124 +    DistMap distMap;
   2.125 +    bfs.distMap(distMap);
   2.126 +    
   2.127 +    bfs.init();
   2.128 +    for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
   2.129 +      if(!bfs.reached(n)) {
   2.130 +	bfs.addSource(n);
   2.131 +	while (!bfs.emptyQueue()) {
   2.132 +	  compMap.set(bfs.nextNode(), compNum);
   2.133 +	  bfs.processNextNode();
   2.134 +	}
   2.135 +	++compNum;
   2.136 +      }
   2.137 +    }
   2.138 +    return compNum;
   2.139 +  }
   2.140 +
   2.141 +  namespace _topology_bits {
   2.142 +
   2.143 +    template <typename Graph, typename Iterator >
   2.144 +    struct LeaveOrderVisitor : public DfsVisitor<Graph> {
   2.145 +    public:
   2.146 +      typedef typename Graph::Node Node;
   2.147 +      LeaveOrderVisitor(Iterator it) : _it(it) {}
   2.148 +
   2.149 +      void leave(const Node& node) {
   2.150 +	*(_it++) = node;
   2.151 +      }
   2.152 +
   2.153 +    private:
   2.154 +      Iterator _it;
   2.155 +    };
   2.156 +
   2.157 +    template <typename Graph, typename Map>
   2.158 +    struct FillMapVisitor : public DfsVisitor<Graph> {
   2.159 +    public:
   2.160 +      typedef typename Graph::Node Node;
   2.161 +      typedef typename Map::Value Value;
   2.162 +
   2.163 +      FillMapVisitor(Map& map, Value& value) 
   2.164 +	: _map(map), _value(value) {}
   2.165 +
   2.166 +      void reach(const Node& node) {
   2.167 +	_map.set(node, _value);
   2.168 +      }
   2.169 +    private:
   2.170 +      Map& _map;
   2.171 +      Value& _value;
   2.172 +    };
   2.173 +
   2.174 +    template <typename Graph, typename EdgeMap>
   2.175 +    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
   2.176 +    public:
   2.177 +      typedef typename Graph::Node Node;
   2.178 +      typedef typename Graph::Edge Edge;
   2.179 +
   2.180 +      StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap, 
   2.181 +				       int& cutNum) 
   2.182 +	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 
   2.183 +	  _compMap(graph), _num(0) {
   2.184 +      }
   2.185 +
   2.186 +      void stop(const Node&) {
   2.187 +	++_num;
   2.188 +      }
   2.189 +
   2.190 +      void reach(const Node& node) {
   2.191 +	_compMap.set(node, _num);
   2.192 +      }
   2.193 +
   2.194 +      void examine(const Edge& edge) {
   2.195 + 	if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) {
   2.196 + 	  _cutMap.set(edge, true);
   2.197 + 	  ++_cutNum;
   2.198 + 	}
   2.199 +      }
   2.200 +    private:
   2.201 +      const Graph& _graph;
   2.202 +      EdgeMap& _cutMap;
   2.203 +      int& _cutNum;
   2.204 +
   2.205 +      typename Graph::template NodeMap<int> _compMap;
   2.206 +      int _num;
   2.207 +    };
   2.208 +
   2.209 +  }
   2.210 +
   2.211 +
   2.212 +  /// \ingroup topology
   2.213 +  ///
   2.214 +  /// \brief Check that the given directed graph is strongly connected.
   2.215 +  ///
   2.216 +  /// Check that the given directed graph is strongly connected. The
   2.217 +  /// graph is strongly connected when any two nodes of the graph are
   2.218 +  /// connected with directed pathes in both direction.
   2.219 +  /// \return %False when the graph is not strongly connected.
   2.220 +  /// \see connected
   2.221 +  ///
   2.222 +  /// \waning Empty graph is not strongly connected.
   2.223 +  template <typename Graph>
   2.224 +  bool stronglyConnected(const Graph& graph) {
   2.225 +    checkConcept<concept::StaticGraph, Graph>();
   2.226 +    if (NodeIt(graph) == INVALID) return false;
   2.227 +
   2.228 +    typedef typename Graph::Node Node;
   2.229 +    typedef typename Graph::NodeIt NodeIt;
   2.230 +
   2.231 +    using namespace _topology_bits;
   2.232 +
   2.233 +    typedef DfsVisitor<Graph> Visitor;
   2.234 +    Visitor visitor;
   2.235 +
   2.236 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
   2.237 +    dfs.init();
   2.238 +    dfs.addSource(NodeIt(graph));
   2.239 +    dfs.start();
   2.240 +
   2.241 +    for (NodeIt it(graph); it != INVALID; ++it) {
   2.242 +      if (!dfs.reached(it)) {
   2.243 +	return false;
   2.244 +      }
   2.245 +    }
   2.246 +
   2.247 +    typedef RevGraphAdaptor<const Graph> RGraph;
   2.248 +    RGraph rgraph(graph);
   2.249 +
   2.250 +    typedef DfsVisitor<Graph> RVisitor;
   2.251 +    RVisitor rvisitor;
   2.252 +
   2.253 +    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
   2.254 +    rdfs.init();    
   2.255 +    rdfs.addSource(NodeIt(graph));
   2.256 +    rdfs.start();
   2.257 +
   2.258 +    for (NodeIt it(graph); it != INVALID; ++it) {
   2.259 +      if (!rdfs.reached(it)) {
   2.260 +	return false;
   2.261 +      }
   2.262 +    }
   2.263 +
   2.264 +    return true;
   2.265 +  }
   2.266 +
   2.267 +  /// \ingroup topology
   2.268 +  ///
   2.269 +  /// \brief Count the strongly connected components of a directed graph
   2.270 +  ///
   2.271 +  /// Count the strongly connected components of a directed graph.
   2.272 +  /// The strongly connected components are the classes of an equivalence
   2.273 +  /// relation on the nodes of the graph. Two nodes are connected with
   2.274 +  /// directed paths in both direction.
   2.275 +  ///
   2.276 +  /// \param g The graph.
   2.277 +  /// \return The number of components
   2.278 +  template <typename Graph>
   2.279 +  int countStronglyConnectedComponents(const Graph& graph) {
   2.280 +    checkConcept<concept::StaticGraph, Graph>();
   2.281 +
   2.282 +    using namespace _topology_bits;
   2.283 +
   2.284 +    typedef typename Graph::Node Node;
   2.285 +    typedef typename Graph::Edge Edge;
   2.286 +    typedef typename Graph::NodeIt NodeIt;
   2.287 +    typedef typename Graph::EdgeIt EdgeIt;
   2.288 +    
   2.289 +    typedef std::vector<Node> Container;
   2.290 +    typedef typename Container::iterator Iterator;
   2.291 +
   2.292 +    Container nodes(countNodes(graph));
   2.293 +    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
   2.294 +    Visitor visitor(nodes.begin());
   2.295 +      
   2.296 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
   2.297 +    dfs.init();
   2.298 +    for (NodeIt it(graph); it != INVALID; ++it) {
   2.299 +      if (!dfs.reached(it)) {
   2.300 +	dfs.addSource(it);
   2.301 +	dfs.start();
   2.302 +      }
   2.303 +    }
   2.304 +
   2.305 +    typedef typename Container::reverse_iterator RIterator;
   2.306 +    typedef RevGraphAdaptor<const Graph> RGraph;
   2.307 +
   2.308 +    RGraph rgraph(graph);
   2.309 +
   2.310 +    typedef DfsVisitor<Graph> RVisitor;
   2.311 +    RVisitor rvisitor;
   2.312 +
   2.313 +    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
   2.314 +
   2.315 +    int compNum = 0;
   2.316 +
   2.317 +    rdfs.init();
   2.318 +    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   2.319 +      if (!rdfs.reached(*it)) {
   2.320 +	rdfs.addSource(*it);
   2.321 +	rdfs.start();
   2.322 +	++compNum;
   2.323 +      }
   2.324 +    }
   2.325 +    return compNum;
   2.326 +  }
   2.327 +
   2.328 +  /// \ingroup topology
   2.329 +  ///
   2.330 +  /// \brief Find the strongly connected components of a directed graph
   2.331 +  ///
   2.332 +  /// Find the strongly connected components of a directed graph.
   2.333 +  /// The strongly connected components are the classes of an equivalence
   2.334 +  /// relation on the nodes of the graph. Two nodes are in relationship
   2.335 +  /// when there are directed paths between them in both direction.
   2.336 +  ///
   2.337 +  /// \param g The graph.
   2.338 +  /// \retval comp A writable node map. The values will be set from 0 to
   2.339 +  /// the number of the strongly connected components minus one. Each values 
   2.340 +  /// of the map will be set exactly once, the values of a certain component 
   2.341 +  /// will be set continuously.
   2.342 +  /// \return The number of components
   2.343 +  template <typename Graph, typename NodeMap>
   2.344 +  int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
   2.345 +    checkConcept<concept::StaticGraph, Graph>();
   2.346 +    typedef typename Graph::Node Node;
   2.347 +    typedef typename Graph::NodeIt NodeIt;
   2.348 +    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
   2.349 +
   2.350 +    using namespace _topology_bits;
   2.351 +    
   2.352 +    typedef std::vector<Node> Container;
   2.353 +    typedef typename Container::iterator Iterator;
   2.354 +
   2.355 +    Container nodes(countNodes(graph));
   2.356 +    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
   2.357 +    Visitor visitor(nodes.begin());
   2.358 +      
   2.359 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
   2.360 +    dfs.init();
   2.361 +    for (NodeIt it(graph); it != INVALID; ++it) {
   2.362 +      if (!dfs.reached(it)) {
   2.363 +	dfs.addSource(it);
   2.364 +	dfs.start();
   2.365 +      }
   2.366 +    }
   2.367 +
   2.368 +    typedef typename Container::reverse_iterator RIterator;
   2.369 +    typedef RevGraphAdaptor<const Graph> RGraph;
   2.370 +
   2.371 +    RGraph rgraph(graph);
   2.372 +
   2.373 +    int compNum = 0;
   2.374 +
   2.375 +    typedef FillMapVisitor<RGraph, NodeMap> RVisitor;
   2.376 +    RVisitor rvisitor(compMap, compNum);
   2.377 +
   2.378 +    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
   2.379 +
   2.380 +    rdfs.init();
   2.381 +    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   2.382 +      if (!rdfs.reached(*it)) {
   2.383 +	rdfs.addSource(*it);
   2.384 +	rdfs.start();
   2.385 +	++compNum;
   2.386 +      }
   2.387 +    }
   2.388 +    return compNum;
   2.389 +  }
   2.390 +
   2.391 +  /// \ingroup topology
   2.392 +  ///
   2.393 +  /// \brief Find the cut edges of the strongly connected components.
   2.394 +  ///
   2.395 +  /// Find the cut edges of the strongly connected components.
   2.396 +  /// The strongly connected components are the classes of an equivalence
   2.397 +  /// relation on the nodes of the graph. Two nodes are in relationship
   2.398 +  /// when there are directed paths between them in both direction.
   2.399 +  /// The strongly connected components are separated by the cut edges.
   2.400 +  ///
   2.401 +  /// \param g The graph.
   2.402 +  /// \retval comp A writable edge map. The values will be set true when
   2.403 +  /// the edge is cut edge otherwise false.
   2.404 +  ///
   2.405 +  /// \return The number of cut edges
   2.406 +  template <typename Graph, typename EdgeMap>
   2.407 +  int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
   2.408 +    checkConcept<concept::StaticGraph, Graph>();
   2.409 +    typedef typename Graph::Node Node;
   2.410 +    typedef typename Graph::Edge Edge;
   2.411 +    typedef typename Graph::NodeIt NodeIt;
   2.412 +    checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>();
   2.413 +
   2.414 +    using namespace _topology_bits;
   2.415 +    
   2.416 +    typedef std::vector<Node> Container;
   2.417 +    typedef typename Container::iterator Iterator;
   2.418 +
   2.419 +    Container nodes(countNodes(graph));
   2.420 +    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
   2.421 +    Visitor visitor(nodes.begin());
   2.422 +      
   2.423 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
   2.424 +    dfs.init();
   2.425 +    for (NodeIt it(graph); it != INVALID; ++it) {
   2.426 +      if (!dfs.reached(it)) {
   2.427 +	dfs.addSource(it);
   2.428 +	dfs.start();
   2.429 +      }
   2.430 +    }
   2.431 +
   2.432 +    typedef typename Container::reverse_iterator RIterator;
   2.433 +    typedef RevGraphAdaptor<const Graph> RGraph;
   2.434 +
   2.435 +    RGraph rgraph(graph);
   2.436 +
   2.437 +    int cutNum = 0;
   2.438 +
   2.439 +    typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;
   2.440 +    RVisitor rvisitor(rgraph, cutMap, cutNum);
   2.441 +
   2.442 +    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
   2.443 +
   2.444 +    rdfs.init();
   2.445 +    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   2.446 +      if (!rdfs.reached(*it)) {
   2.447 +	rdfs.addSource(*it);
   2.448 +	rdfs.start();
   2.449 +      }
   2.450 +    }
   2.451 +    return cutNum;
   2.452 +  }
   2.453 +
   2.454    namespace _topology_bits {
   2.455      
   2.456 -    template <typename NodeMap>
   2.457 -    class BackCounterMap {
   2.458 +    template <typename Graph>
   2.459 +    class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
   2.460      public:
   2.461 -      BackCounterMap(NodeMap& _nodeMap, int _counter)
   2.462 -	: nodeMap(_nodeMap), counter(_counter) {}
   2.463 +      typedef typename Graph::Node Node;
   2.464 +      typedef typename Graph::Edge Edge;
   2.465 +      typedef typename Graph::UndirEdge UndirEdge;
   2.466  
   2.467 -      void set(typename NodeMap::Key key, bool val) {
   2.468 -	if (val) {
   2.469 -	  nodeMap.set(key, --counter);
   2.470 -	} else {
   2.471 -	  nodeMap.set(key, -1);
   2.472 +      CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) 
   2.473 +	: _graph(graph), _compNum(compNum), 
   2.474 +	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   2.475 +
   2.476 +      void start(const Node& node) {
   2.477 +	_predMap.set(node, INVALID);
   2.478 +      }
   2.479 +      
   2.480 +      void reach(const Node& node) {
   2.481 +	_numMap.set(node, _num);
   2.482 +	_retMap.set(node, _num);
   2.483 +	++_num;
   2.484 +      }
   2.485 +
   2.486 +      void discover(const Edge& edge) {
   2.487 +	_predMap.set(_graph.target(edge), _graph.source(edge));
   2.488 +      }
   2.489 +
   2.490 +      void examine(const Edge& edge) {
   2.491 +	if (_graph.source(edge) == _graph.target(edge) && 
   2.492 +	    _graph.direction(edge)) {
   2.493 +	  ++_compNum;
   2.494 +	  return;
   2.495 +	}
   2.496 +	if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
   2.497 +	  return;
   2.498 +	}
   2.499 +	if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
   2.500 +	  _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
   2.501  	}
   2.502        }
   2.503  
   2.504 -      bool operator[](typename NodeMap::Key key) const {
   2.505 -	return nodeMap[key] != -1;
   2.506 +      void backtrack(const Edge& edge) {
   2.507 +	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   2.508 +	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   2.509 +	}  
   2.510 +	if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
   2.511 +	  ++_compNum;
   2.512 +	}
   2.513 +      }
   2.514 +      
   2.515 +    private:
   2.516 +      const Graph& _graph;
   2.517 +      int& _compNum; 
   2.518 +
   2.519 +      typename Graph::template NodeMap<int> _numMap;
   2.520 +      typename Graph::template NodeMap<int> _retMap;
   2.521 +      typename Graph::template NodeMap<Node> _predMap;
   2.522 +      int _num;
   2.523 +    };
   2.524 +
   2.525 +    template <typename Graph, typename EdgeMap>
   2.526 +    class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
   2.527 +    public:
   2.528 +      typedef typename Graph::Node Node;
   2.529 +      typedef typename Graph::Edge Edge;
   2.530 +      typedef typename Graph::UndirEdge UndirEdge;
   2.531 +
   2.532 +      NodeBiconnectedComponentsVisitor(const Graph& graph, 
   2.533 +				       EdgeMap& compMap, int &compNum) 
   2.534 +	: _graph(graph), _compMap(compMap), _compNum(compNum), 
   2.535 +	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   2.536 +
   2.537 +      void start(const Node& node) {
   2.538 +	_predMap.set(node, INVALID);
   2.539 +      }
   2.540 +      
   2.541 +      void reach(const Node& node) {
   2.542 +	_numMap.set(node, _num);
   2.543 +	_retMap.set(node, _num);
   2.544 +	++_num;
   2.545 +      }
   2.546 +
   2.547 +      void discover(const Edge& edge) {
   2.548 +	Node target = _graph.target(edge);
   2.549 +	_predMap.set(target, edge);
   2.550 +	_edgeStack.push(edge);
   2.551 +      }
   2.552 +
   2.553 +      void examine(const Edge& edge) {
   2.554 +	Node source = _graph.source(edge);
   2.555 +	Node target = _graph.target(edge);
   2.556 +	if (source == target && _graph.direction(edge)) {
   2.557 +	  _compMap.set(edge, _compNum);
   2.558 +	  ++_compNum;
   2.559 +	  return;
   2.560 +	}
   2.561 +	if (_numMap[target] < _numMap[source]) {
   2.562 +	  if (_predMap[source] != _graph.oppositeEdge(edge)) {
   2.563 +	    _edgeStack.push(edge);
   2.564 +	  }
   2.565 +	}
   2.566 +	if (_predMap[source] != INVALID && 
   2.567 +	    target == _graph.source(_predMap[source])) {
   2.568 +	  return;
   2.569 +	}
   2.570 +	if (_retMap[source] > _numMap[target]) {
   2.571 +	  _retMap.set(source, _numMap[target]);
   2.572 +	}
   2.573 +      }
   2.574 +
   2.575 +      void backtrack(const Edge& edge) {
   2.576 +	Node source = _graph.source(edge);
   2.577 +	Node target = _graph.target(edge);
   2.578 +	if (_retMap[source] > _retMap[target]) {
   2.579 +	  _retMap.set(source, _retMap[target]);
   2.580 +	}  
   2.581 +	if (_numMap[source] <= _retMap[target]) {
   2.582 +	  while (_edgeStack.top() != edge) {
   2.583 +	    _compMap.set(_edgeStack.top(), _compNum);
   2.584 +	    _edgeStack.pop();
   2.585 +	  }
   2.586 +	  _compMap.set(edge, _compNum);
   2.587 +	  _edgeStack.pop();
   2.588 +	  ++_compNum;
   2.589 +	}
   2.590 +      }
   2.591 +      
   2.592 +    private:
   2.593 +      const Graph& _graph;
   2.594 +      EdgeMap& _compMap;
   2.595 +      int& _compNum; 
   2.596 +
   2.597 +      typename Graph::template NodeMap<int> _numMap;
   2.598 +      typename Graph::template NodeMap<int> _retMap;
   2.599 +      typename Graph::template NodeMap<Edge> _predMap;
   2.600 +      std::stack<UndirEdge> _edgeStack;
   2.601 +      int _num;
   2.602 +    };
   2.603 +
   2.604 +
   2.605 +    template <typename Graph, typename NodeMap>
   2.606 +    class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {
   2.607 +    public:
   2.608 +      typedef typename Graph::Node Node;
   2.609 +      typedef typename Graph::Edge Edge;
   2.610 +      typedef typename Graph::UndirEdge UndirEdge;
   2.611 +
   2.612 +      NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
   2.613 +				     int& cutNum) 
   2.614 +	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
   2.615 +	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   2.616 +
   2.617 +      void start(const Node& node) {
   2.618 +	_predMap.set(node, INVALID);
   2.619 +	rootCut = false;
   2.620 +      }
   2.621 +      
   2.622 +      void reach(const Node& node) {
   2.623 +	_numMap.set(node, _num);
   2.624 +	_retMap.set(node, _num);
   2.625 +	++_num;
   2.626 +      }
   2.627 +
   2.628 +      void discover(const Edge& edge) {
   2.629 +	_predMap.set(_graph.target(edge), _graph.source(edge));
   2.630 +      }
   2.631 +
   2.632 +      void examine(const Edge& edge) {
   2.633 +	if (_graph.source(edge) == _graph.target(edge) && 
   2.634 +	    _graph.direction(edge)) {
   2.635 +	  if (!_cutMap[_graph.source(edge)]) {
   2.636 +	    _cutMap.set(_graph.source(edge), true);
   2.637 +	    ++_cutNum;
   2.638 +	  }
   2.639 +	  return;
   2.640 +	}
   2.641 +	if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
   2.642 +	if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
   2.643 +	  _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
   2.644 +	}
   2.645 +      }
   2.646 +
   2.647 +      void backtrack(const Edge& edge) {
   2.648 +	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   2.649 +	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   2.650 +	}  
   2.651 +	if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
   2.652 +	  if (_predMap[_graph.source(edge)] != INVALID) {
   2.653 +	    if (!_cutMap[_graph.source(edge)]) {
   2.654 +	      _cutMap.set(_graph.source(edge), true);
   2.655 +	      ++_cutNum;
   2.656 +	    }
   2.657 +	  } else if (rootCut) {
   2.658 +	    if (!_cutMap[_graph.source(edge)]) {
   2.659 +	      _cutMap.set(_graph.source(edge), true);
   2.660 +	      ++_cutNum;
   2.661 +	    }
   2.662 +	  } else {
   2.663 +	    rootCut = true;
   2.664 +	  }
   2.665 +	}
   2.666 +      }
   2.667 +      
   2.668 +    private:
   2.669 +      const Graph& _graph;
   2.670 +      NodeMap& _cutMap;
   2.671 +      int& _cutNum; 
   2.672 +
   2.673 +      typename Graph::template NodeMap<int> _numMap;
   2.674 +      typename Graph::template NodeMap<int> _retMap;
   2.675 +      typename Graph::template NodeMap<Node> _predMap;
   2.676 +      std::stack<UndirEdge> _edgeStack;
   2.677 +      int _num;
   2.678 +      bool rootCut;
   2.679 +    };
   2.680 +
   2.681 +  }
   2.682 +
   2.683 +  template <typename UndirGraph>
   2.684 +  int countNodeBiconnectedComponents(const UndirGraph& graph);
   2.685 +
   2.686 +  /// \ingroup topology
   2.687 +  ///
   2.688 +  /// \brief Checks the graph is node biconnected.
   2.689 +  ///
   2.690 +  /// This function checks that the undirected graph is node biconnected  
   2.691 +  /// graph. The graph is node biconnected if any two undirected edge is 
   2.692 +  /// on same circle.
   2.693 +  ///
   2.694 +  /// \param graph The graph.
   2.695 +  /// \return %True when the graph node biconnected.
   2.696 +  /// \todo Make it faster.
   2.697 +  template <typename UndirGraph>
   2.698 +  bool nodeBiconnected(const UndirGraph& graph) {
   2.699 +    return countNodeBiconnectedComponents(graph) == 1;
   2.700 +  }
   2.701 +
   2.702 +  /// \ingroup topology
   2.703 +  ///
   2.704 +  /// \brief Count the biconnected components.
   2.705 +  ///
   2.706 +  /// This function finds the node biconnected components in an undirected 
   2.707 +  /// graph. The biconnected components are the classes of an equivalence 
   2.708 +  /// relation on the undirected edges. Two undirected edge is in relationship
   2.709 +  /// when they are on same circle.
   2.710 +  ///
   2.711 +  /// \param graph The graph.
   2.712 +  /// \return The number of components.
   2.713 +  template <typename UndirGraph>
   2.714 +  int countNodeBiconnectedComponents(const UndirGraph& graph) {
   2.715 +    checkConcept<concept::UndirGraph, UndirGraph>();
   2.716 +    typedef typename UndirGraph::NodeIt NodeIt;
   2.717 +
   2.718 +    using namespace _topology_bits;
   2.719 +
   2.720 +    typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;
   2.721 +
   2.722 +    int compNum = 0;
   2.723 +    Visitor visitor(graph, compNum);
   2.724 +
   2.725 +    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
   2.726 +    dfs.init();
   2.727 +    
   2.728 +    for (NodeIt it(graph); it != INVALID; ++it) {
   2.729 +      if (!dfs.reached(it)) {
   2.730 +	dfs.addSource(it);
   2.731 +	dfs.start();
   2.732 +      }
   2.733 +    }
   2.734 +    return compNum;
   2.735 +  }
   2.736 +
   2.737 +  /// \ingroup topology
   2.738 +  ///
   2.739 +  /// \brief Find the node biconnected components.
   2.740 +  ///
   2.741 +  /// This function finds the node biconnected components in an undirected 
   2.742 +  /// graph. The node biconnected components are the classes of an equivalence
   2.743 +  /// relation on the undirected edges. Two undirected edge are in relationship
   2.744 +  /// when they are on same circle.
   2.745 +  ///
   2.746 +  /// \param graph The graph.
   2.747 +  /// \retval comp A writable undir edge map. The values will be set from 0 to
   2.748 +  /// the number of the biconnected components minus one. Each values 
   2.749 +  /// of the map will be set exactly once, the values of a certain component 
   2.750 +  /// will be set continuously.
   2.751 +  /// \return The number of components.
   2.752 +  template <typename UndirGraph, typename UndirEdgeMap>
   2.753 +  int nodeBiconnectedComponents(const UndirGraph& graph, 
   2.754 +				UndirEdgeMap& compMap) {
   2.755 +    checkConcept<concept::UndirGraph, UndirGraph>();
   2.756 +    typedef typename UndirGraph::NodeIt NodeIt;
   2.757 +    typedef typename UndirGraph::UndirEdge UndirEdge;
   2.758 +    checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>();
   2.759 +
   2.760 +    using namespace _topology_bits;
   2.761 +
   2.762 +    typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
   2.763 +    
   2.764 +    int compNum = 0;
   2.765 +    Visitor visitor(graph, compMap, compNum);
   2.766 +
   2.767 +    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
   2.768 +    dfs.init();
   2.769 +    
   2.770 +    for (NodeIt it(graph); it != INVALID; ++it) {
   2.771 +      if (!dfs.reached(it)) {
   2.772 +	dfs.addSource(it);
   2.773 +	dfs.start();
   2.774 +      }
   2.775 +    }
   2.776 +    return compNum;
   2.777 +  }
   2.778 +
   2.779 +  /// \ingroup topology
   2.780 +  ///
   2.781 +  /// \brief Find the node biconnected cut nodes.
   2.782 +  ///
   2.783 +  /// This function finds the node biconnected cut nodes in an undirected 
   2.784 +  /// graph. The node biconnected components are the classes of an equivalence
   2.785 +  /// relation on the undirected edges. Two undirected edges are in 
   2.786 +  /// relationship when they are on same circle. The biconnected components 
   2.787 +  /// are separted by nodes which are the cut nodes of the components.
   2.788 +  ///
   2.789 +  /// \param graph The graph.
   2.790 +  /// \retval comp A writable edge map. The values will be set true when
   2.791 +  /// the node separate two or more components.
   2.792 +  /// \return The number of the cut nodes.
   2.793 +  template <typename UndirGraph, typename NodeMap>
   2.794 +  int nodeBiconnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {
   2.795 +    checkConcept<concept::UndirGraph, UndirGraph>();
   2.796 +    typedef typename UndirGraph::Node Node;
   2.797 +    typedef typename UndirGraph::NodeIt NodeIt;
   2.798 +    checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
   2.799 +
   2.800 +    using namespace _topology_bits;
   2.801 +
   2.802 +    typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
   2.803 +    
   2.804 +    int cutNum = 0;
   2.805 +    Visitor visitor(graph, cutMap, cutNum);
   2.806 +
   2.807 +    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
   2.808 +    dfs.init();
   2.809 +    
   2.810 +    for (NodeIt it(graph); it != INVALID; ++it) {
   2.811 +      if (!dfs.reached(it)) {
   2.812 +	dfs.addSource(it);
   2.813 +	dfs.start();
   2.814 +      }
   2.815 +    }
   2.816 +    return cutNum;
   2.817 +  }
   2.818 +
   2.819 +  namespace _topology_bits {
   2.820 +    
   2.821 +    template <typename Graph>
   2.822 +    class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
   2.823 +    public:
   2.824 +      typedef typename Graph::Node Node;
   2.825 +      typedef typename Graph::Edge Edge;
   2.826 +      typedef typename Graph::UndirEdge UndirEdge;
   2.827 +
   2.828 +      CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) 
   2.829 +	: _graph(graph), _compNum(compNum), 
   2.830 +	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   2.831 +
   2.832 +      void start(const Node& node) {
   2.833 +	_predMap.set(node, INVALID);
   2.834 +      }
   2.835 +      
   2.836 +      void reach(const Node& node) {
   2.837 +	_numMap.set(node, _num);
   2.838 +	_retMap.set(node, _num);
   2.839 +	++_num;
   2.840 +      }
   2.841 +      
   2.842 +      void leave(const Node& node) {
   2.843 +	if (_numMap[node] <= _retMap[node]) {
   2.844 +	  ++_compNum;
   2.845 +	}	
   2.846 +      }
   2.847 +
   2.848 +      void discover(const Edge& edge) {
   2.849 +	_predMap.set(_graph.target(edge), edge);
   2.850 +      }
   2.851 +
   2.852 +      void examine(const Edge& edge) {
   2.853 +	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
   2.854 +	  return;
   2.855 +	}
   2.856 +	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   2.857 +	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   2.858 +	}
   2.859 +      }
   2.860 +
   2.861 +      void backtrack(const Edge& edge) {
   2.862 +	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   2.863 +	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   2.864 +	}  
   2.865 +      }
   2.866 +      
   2.867 +    private:
   2.868 +      const Graph& _graph;
   2.869 +      int& _compNum; 
   2.870 +
   2.871 +      typename Graph::template NodeMap<int> _numMap;
   2.872 +      typename Graph::template NodeMap<int> _retMap;
   2.873 +      typename Graph::template NodeMap<Edge> _predMap;
   2.874 +      int _num;
   2.875 +    };
   2.876 +
   2.877 +    template <typename Graph, typename NodeMap>
   2.878 +    class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
   2.879 +    public:
   2.880 +      typedef typename Graph::Node Node;
   2.881 +      typedef typename Graph::Edge Edge;
   2.882 +      typedef typename Graph::UndirEdge UndirEdge;
   2.883 +
   2.884 +      EdgeBiconnectedComponentsVisitor(const Graph& graph, 
   2.885 +				       NodeMap& compMap, int &compNum) 
   2.886 +	: _graph(graph), _compMap(compMap), _compNum(compNum), 
   2.887 +	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   2.888 +
   2.889 +      void start(const Node& node) {
   2.890 +	_predMap.set(node, INVALID);
   2.891 +      }
   2.892 +      
   2.893 +      void reach(const Node& node) {
   2.894 +	_numMap.set(node, _num);
   2.895 +	_retMap.set(node, _num);
   2.896 +	_nodeStack.push(node);
   2.897 +	++_num;
   2.898 +      }
   2.899 +      
   2.900 +      void leave(const Node& node) {
   2.901 +	if (_numMap[node] <= _retMap[node]) {
   2.902 +	  while (_nodeStack.top() != node) {
   2.903 +	    _compMap.set(_nodeStack.top(), _compNum);
   2.904 +	    _nodeStack.pop();
   2.905 +	  }
   2.906 +	  _compMap.set(node, _compNum);
   2.907 +	  _nodeStack.pop();
   2.908 +	  ++_compNum;
   2.909 +	}	
   2.910 +      }
   2.911 +
   2.912 +      void discover(const Edge& edge) {
   2.913 +	_predMap.set(_graph.target(edge), edge);
   2.914 +      }
   2.915 +
   2.916 +      void examine(const Edge& edge) {
   2.917 +	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
   2.918 +	  return;
   2.919 +	}
   2.920 +	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   2.921 +	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   2.922 +	}
   2.923 +      }
   2.924 +
   2.925 +      void backtrack(const Edge& edge) {
   2.926 +	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   2.927 +	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   2.928 +	}  
   2.929 +      }
   2.930 +      
   2.931 +    private:
   2.932 +      const Graph& _graph;
   2.933 +      NodeMap& _compMap;
   2.934 +      int& _compNum; 
   2.935 +
   2.936 +      typename Graph::template NodeMap<int> _numMap;
   2.937 +      typename Graph::template NodeMap<int> _retMap;
   2.938 +      typename Graph::template NodeMap<Edge> _predMap;
   2.939 +      std::stack<Node> _nodeStack;
   2.940 +      int _num;
   2.941 +    };
   2.942 +
   2.943 +
   2.944 +    template <typename Graph, typename EdgeMap>
   2.945 +    class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {
   2.946 +    public:
   2.947 +      typedef typename Graph::Node Node;
   2.948 +      typedef typename Graph::Edge Edge;
   2.949 +      typedef typename Graph::UndirEdge UndirEdge;
   2.950 +
   2.951 +      EdgeBiconnectedCutEdgesVisitor(const Graph& graph, 
   2.952 +				     EdgeMap& cutMap, int &cutNum) 
   2.953 +	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 
   2.954 +	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   2.955 +
   2.956 +      void start(const Node& node) {
   2.957 +	_predMap[node] = INVALID;
   2.958 +      }
   2.959 +      
   2.960 +      void reach(const Node& node) {
   2.961 +	_numMap.set(node, _num);
   2.962 +	_retMap.set(node, _num);
   2.963 +	++_num;
   2.964 +      }
   2.965 +      
   2.966 +      void leave(const Node& node) {
   2.967 +	if (_numMap[node] <= _retMap[node]) {
   2.968 +	  if (_predMap[node] != INVALID) {
   2.969 +	    _cutMap.set(_predMap[node], true);
   2.970 +	    ++_cutNum;
   2.971 +	  }
   2.972 +	}	
   2.973 +      }
   2.974 +
   2.975 +      void discover(const Edge& edge) {
   2.976 +	_predMap.set(_graph.target(edge), edge);
   2.977 +      }
   2.978 +
   2.979 +      void examine(const Edge& edge) {
   2.980 +	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
   2.981 +	  return;
   2.982 +	}
   2.983 +	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   2.984 +	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   2.985 +	}
   2.986 +      }
   2.987 +
   2.988 +      void backtrack(const Edge& edge) {
   2.989 +	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   2.990 +	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   2.991 +	}  
   2.992 +      }
   2.993 +      
   2.994 +    private:
   2.995 +      const Graph& _graph;
   2.996 +      EdgeMap& _cutMap;
   2.997 +      int& _cutNum; 
   2.998 +
   2.999 +      typename Graph::template NodeMap<int> _numMap;
  2.1000 +      typename Graph::template NodeMap<int> _retMap;
  2.1001 +      typename Graph::template NodeMap<Edge> _predMap;
  2.1002 +      int _num;
  2.1003 +    };
  2.1004 +  }
  2.1005 +
  2.1006 +  template <typename UndirGraph>
  2.1007 +  int countEdgeBiconnectedComponents(const UndirGraph& graph);
  2.1008 +
  2.1009 +  /// \ingroup topology
  2.1010 +  ///
  2.1011 +  /// \brief Checks that the graph is edge biconnected.
  2.1012 +  ///
  2.1013 +  /// This function checks that the graph is edge biconnected. The undirected
  2.1014 +  /// graph is edge biconnected when any two nodes are connected with two
  2.1015 +  /// edge-disjoint paths.
  2.1016 +  ///
  2.1017 +  /// \param graph The undirected graph.
  2.1018 +  /// \return The number of components.
  2.1019 +  /// \todo Make it faster.
  2.1020 +  template <typename UndirGraph>
  2.1021 +  bool edgeBiconnected(const UndirGraph& graph) { 
  2.1022 +    return countEdgeBiconnectedComponents(graph) == 1;
  2.1023 +  }
  2.1024 +
  2.1025 +  /// \ingroup topology
  2.1026 +  ///
  2.1027 +  /// \brief Count the edge biconnected components.
  2.1028 +  ///
  2.1029 +  /// This function count the edge biconnected components in an undirected 
  2.1030 +  /// graph. The edge biconnected components are the classes of an equivalence
  2.1031 +  /// relation on the nodes. Two nodes are in relationship when they are  
  2.1032 +  /// connected with at least two edge-disjoint paths.
  2.1033 +  ///
  2.1034 +  /// \param graph The undirected graph.
  2.1035 +  /// \return The number of components.
  2.1036 +  template <typename UndirGraph>
  2.1037 +  int countEdgeBiconnectedComponents(const UndirGraph& graph) { 
  2.1038 +    checkConcept<concept::UndirGraph, UndirGraph>();
  2.1039 +    typedef typename UndirGraph::NodeIt NodeIt;
  2.1040 +
  2.1041 +    using namespace _topology_bits;
  2.1042 +
  2.1043 +    typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;
  2.1044 +    
  2.1045 +    int compNum = 0;
  2.1046 +    Visitor visitor(graph, compNum);
  2.1047 +
  2.1048 +    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
  2.1049 +    dfs.init();
  2.1050 +    
  2.1051 +    for (NodeIt it(graph); it != INVALID; ++it) {
  2.1052 +      if (!dfs.reached(it)) {
  2.1053 +	dfs.addSource(it);
  2.1054 +	dfs.start();
  2.1055 +      }
  2.1056 +    }
  2.1057 +    return compNum;
  2.1058 +  }
  2.1059 +
  2.1060 +  /// \ingroup topology
  2.1061 +  ///
  2.1062 +  /// \brief Find the edge biconnected components.
  2.1063 +  ///
  2.1064 +  /// This function finds the edge biconnected components in an undirected 
  2.1065 +  /// graph. The edge biconnected components are the classes of an equivalence
  2.1066 +  /// relation on the nodes. Two nodes are in relationship when they are  
  2.1067 +  /// connected at least two edge-disjoint paths.
  2.1068 +  ///
  2.1069 +  /// \param graph The graph.
  2.1070 +  /// \retval comp A writable node map. The values will be set from 0 to
  2.1071 +  /// the number of the biconnected components minus one. Each values 
  2.1072 +  /// of the map will be set exactly once, the values of a certain component 
  2.1073 +  /// will be set continuously.
  2.1074 +  /// \return The number of components.
  2.1075 +  template <typename UndirGraph, typename NodeMap>
  2.1076 +  int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) { 
  2.1077 +    checkConcept<concept::UndirGraph, UndirGraph>();
  2.1078 +    typedef typename UndirGraph::NodeIt NodeIt;
  2.1079 +    typedef typename UndirGraph::Node Node;
  2.1080 +    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
  2.1081 +
  2.1082 +    using namespace _topology_bits;
  2.1083 +
  2.1084 +    typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
  2.1085 +    
  2.1086 +    int compNum = 0;
  2.1087 +    Visitor visitor(graph, compMap, compNum);
  2.1088 +
  2.1089 +    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
  2.1090 +    dfs.init();
  2.1091 +    
  2.1092 +    for (NodeIt it(graph); it != INVALID; ++it) {
  2.1093 +      if (!dfs.reached(it)) {
  2.1094 +	dfs.addSource(it);
  2.1095 +	dfs.start();
  2.1096 +      }
  2.1097 +    }
  2.1098 +    return compNum;
  2.1099 +  }
  2.1100 +
  2.1101 +  /// \ingroup topology
  2.1102 +  ///
  2.1103 +  /// \brief Find the edge biconnected cut edges.
  2.1104 +  ///
  2.1105 +  /// This function finds the edge biconnected components in an undirected 
  2.1106 +  /// graph. The edge biconnected components are the classes of an equivalence
  2.1107 +  /// relation on the nodes. Two nodes are in relationship when they are 
  2.1108 +  /// connected with at least two edge-disjoint paths. The edge biconnected 
  2.1109 +  /// components are separted by edges which are the cut edges of the 
  2.1110 +  /// components.
  2.1111 +  ///
  2.1112 +  /// \param graph The graph.
  2.1113 +  /// \retval comp A writable node map. The values will be set true when the
  2.1114 +  /// edge is a cut edge.
  2.1115 +  /// \return The number of cut edges.
  2.1116 +  template <typename UndirGraph, typename UndirEdgeMap>
  2.1117 +  int edgeBiconnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { 
  2.1118 +    checkConcept<concept::UndirGraph, UndirGraph>();
  2.1119 +    typedef typename UndirGraph::NodeIt NodeIt;
  2.1120 +    typedef typename UndirGraph::UndirEdge UndirEdge;
  2.1121 +    checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>();
  2.1122 +
  2.1123 +    using namespace _topology_bits;
  2.1124 +
  2.1125 +    typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
  2.1126 +    
  2.1127 +    int cutNum = 0;
  2.1128 +    Visitor visitor(graph, cutMap, cutNum);
  2.1129 +
  2.1130 +    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
  2.1131 +    dfs.init();
  2.1132 +    
  2.1133 +    for (NodeIt it(graph); it != INVALID; ++it) {
  2.1134 +      if (!dfs.reached(it)) {
  2.1135 +	dfs.addSource(it);
  2.1136 +	dfs.start();
  2.1137 +      }
  2.1138 +    }
  2.1139 +    return cutNum;
  2.1140 +  }
  2.1141 +
  2.1142 +
  2.1143 +  namespace _topology_bits {
  2.1144 +    
  2.1145 +    template <typename Graph, typename IntNodeMap>
  2.1146 +    class TopologicalSortVisitor : public DfsVisitor<Graph> {
  2.1147 +    public:
  2.1148 +      typedef typename Graph::Node Node;
  2.1149 +      typedef typename Graph::Edge edge;
  2.1150 +
  2.1151 +      TopologicalSortVisitor(IntNodeMap& order, int num) 
  2.1152 +	: _order(order), _num(num) {}
  2.1153 +      
  2.1154 +      void leave(const Node& node) {
  2.1155 +	_order.set(node, --_num);
  2.1156        }
  2.1157  
  2.1158      private:
  2.1159 -      NodeMap& nodeMap;
  2.1160 -      int counter;
  2.1161 +      IntNodeMap& _order;
  2.1162 +      int _num;
  2.1163      };
  2.1164 +    
  2.1165    }
  2.1166  
  2.1167 -  // \todo Its to special output // ReadWriteMap
  2.1168 +  /// \ingroup topology
  2.1169 +  ///
  2.1170 +  /// \brief Sort the nodes of a DAG into topolgical order.
  2.1171 +  ///
  2.1172 +  /// Sort the nodes of a DAG into topolgical order.
  2.1173 +  ///
  2.1174 +  /// \param g The graph. In must be directed and acyclic.
  2.1175 +  /// \retval comp A writable node map. The values will be set from 0 to
  2.1176 +  /// the number of the nodes in the graph minus one. Each values of the map
  2.1177 +  /// will be set exactly once, the values  will be set descending order.
  2.1178 +  ///
  2.1179 +  /// \see checkedTopologicalSort
  2.1180 +  /// \see dag
  2.1181    template <typename Graph, typename NodeMap>
  2.1182 -  bool topological_sort(const Graph& graph, NodeMap& nodeMap) {
  2.1183 +  void topologicalSort(const Graph& graph, NodeMap& order) {
  2.1184 +    using namespace _topology_bits;
  2.1185 +
  2.1186 +    checkConcept<concept::StaticGraph, Graph>();
  2.1187 +    checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
  2.1188 +
  2.1189 +    typedef typename Graph::Node Node;
  2.1190 +    typedef typename Graph::NodeIt NodeIt;
  2.1191 +    typedef typename Graph::Edge Edge;
  2.1192 +
  2.1193 +    TopologicalSortVisitor<Graph, NodeMap> 
  2.1194 +      visitor(order, countNodes(graph)); 
  2.1195 +
  2.1196 +    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
  2.1197 +      dfs(graph, visitor);
  2.1198 +
  2.1199 +    dfs.init();
  2.1200 +    for (NodeIt it(graph); it != INVALID; ++it) {
  2.1201 +      if (!dfs.reached(it)) {
  2.1202 +	dfs.addSource(it);
  2.1203 +	dfs.start();
  2.1204 +      }
  2.1205 +    }    
  2.1206 +  }
  2.1207 +
  2.1208 +  /// \ingroup topology
  2.1209 +  ///
  2.1210 +  /// \brief Sort the nodes of a DAG into topolgical order.
  2.1211 +  ///
  2.1212 +  /// Sort the nodes of a DAG into topolgical order. It also checks
  2.1213 +  /// that the given graph is DAG.
  2.1214 +  ///
  2.1215 +  /// \param g The graph. In must be directed and acyclic.
  2.1216 +  /// \retval order A readable - writable node map. The values will be set 
  2.1217 +  /// from 0 to the number of the nodes in the graph minus one. Each values 
  2.1218 +  /// of the map will be set exactly once, the values will be set descending 
  2.1219 +  /// order.
  2.1220 +  /// \return %False when the graph is not DAG.
  2.1221 +  ///
  2.1222 +  /// \see topologicalSort
  2.1223 +  /// \see dag
  2.1224 +  template <typename Graph, typename NodeMap>
  2.1225 +  bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
  2.1226      using namespace _topology_bits;
  2.1227  
  2.1228      checkConcept<concept::StaticGraph, Graph>();
  2.1229 @@ -72,35 +1231,39 @@
  2.1230      typedef typename Graph::NodeIt NodeIt;
  2.1231      typedef typename Graph::Edge Edge;
  2.1232  
  2.1233 -    typedef BackCounterMap<NodeMap> ProcessedMap;
  2.1234 +    order = constMap<Node, int, -1>();
  2.1235  
  2.1236 -    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
  2.1237 -      Create dfs(graph);
  2.1238 +    TopologicalSortVisitor<Graph, NodeMap> 
  2.1239 +      visitor(order, countNodes(graph)); 
  2.1240  
  2.1241 -    ProcessedMap processed(nodeMap, countNodes(graph));
  2.1242 +    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
  2.1243 +      dfs(graph, visitor);
  2.1244  
  2.1245 -    dfs.processedMap(processed);
  2.1246      dfs.init();
  2.1247      for (NodeIt it(graph); it != INVALID; ++it) {
  2.1248        if (!dfs.reached(it)) {
  2.1249  	dfs.addSource(it);
  2.1250  	while (!dfs.emptyQueue()) {
  2.1251 -	  Edge edge = dfs.nextEdge();
  2.1252 -	  Node target = graph.target(edge);
  2.1253 -	  if (dfs.reached(target) && !processed[target]) {
  2.1254 -	    return false;
  2.1255 -	  }
  2.1256 -	  dfs.processNextEdge();
  2.1257 -	}
  2.1258 + 	  Edge edge = dfs.nextEdge();
  2.1259 + 	  Node target = graph.target(edge);
  2.1260 + 	  if (dfs.reached(target) && order[target] == -1) {
  2.1261 + 	    return false;
  2.1262 + 	  }
  2.1263 + 	  dfs.processNextEdge();
  2.1264 + 	}
  2.1265        }
  2.1266 -    }    
  2.1267 +    }
  2.1268      return true;
  2.1269    }
  2.1270  
  2.1271 -  /// \brief Check that the given graph is a DAG.
  2.1272 +  /// \ingroup topology
  2.1273    ///
  2.1274 -  /// Check that the given graph is a DAG. The DAG is
  2.1275 +  /// \brief Check that the given directed graph is a DAG.
  2.1276 +  ///
  2.1277 +  /// Check that the given directed graph is a DAG. The DAG is
  2.1278    /// an Directed Acyclic Graph.
  2.1279 +  /// \return %False when the graph is not DAG.
  2.1280 +  /// \see acyclic
  2.1281    template <typename Graph>
  2.1282    bool dag(const Graph& graph) {
  2.1283  
  2.1284 @@ -135,29 +1298,14 @@
  2.1285      return true;
  2.1286    }
  2.1287  
  2.1288 -  // UndirGraph algorithms
  2.1289 -
  2.1290 -  /// \brief Check that the given undirected graph is connected.
  2.1291 +  /// \ingroup topology
  2.1292    ///
  2.1293 -  /// Check that the given undirected graph connected.
  2.1294 -  template <typename UndirGraph>
  2.1295 -  bool connected(const UndirGraph& graph) {
  2.1296 -    checkConcept<concept::UndirGraph, UndirGraph>();
  2.1297 -    typedef typename UndirGraph::NodeIt NodeIt;
  2.1298 -    if (NodeIt(graph) == INVALID) return false;
  2.1299 -    Dfs<UndirGraph> dfs(graph);
  2.1300 -    dfs.run(NodeIt(graph));
  2.1301 -    for (NodeIt it(graph); it != INVALID; ++it) {
  2.1302 -      if (!dfs.reached(it)) {
  2.1303 -	return false;
  2.1304 -      }
  2.1305 -    }
  2.1306 -    return true;
  2.1307 -  }
  2.1308 -
  2.1309    /// \brief Check that the given undirected graph is acyclic.
  2.1310    ///
  2.1311    /// Check that the given undirected graph acyclic.
  2.1312 +  /// \param graph The undirected graph.
  2.1313 +  /// \return %True when there is no circle in the graph.
  2.1314 +  /// \see dag
  2.1315    template <typename UndirGraph>
  2.1316    bool acyclic(const UndirGraph& graph) {
  2.1317      checkConcept<concept::UndirGraph, UndirGraph>();
  2.1318 @@ -184,16 +1332,19 @@
  2.1319      return true;
  2.1320    }
  2.1321  
  2.1322 +  /// \ingroup topology
  2.1323 +  ///
  2.1324    /// \brief Check that the given undirected graph is tree.
  2.1325    ///
  2.1326    /// Check that the given undirected graph is tree.
  2.1327 +  /// \param graph The undirected graph.
  2.1328 +  /// \return %True when the graph is acyclic and connected.
  2.1329    template <typename UndirGraph>
  2.1330    bool tree(const UndirGraph& graph) {
  2.1331      checkConcept<concept::UndirGraph, UndirGraph>();
  2.1332      typedef typename UndirGraph::Node Node;
  2.1333      typedef typename UndirGraph::NodeIt NodeIt;
  2.1334      typedef typename UndirGraph::Edge Edge;
  2.1335 -    if (NodeIt(graph) == INVALID) return false;
  2.1336      Dfs<UndirGraph> dfs(graph);
  2.1337      dfs.init();
  2.1338      dfs.addSource(NodeIt(graph));
  2.1339 @@ -214,208 +1365,45 @@
  2.1340      }    
  2.1341      return true;
  2.1342    }
  2.1343 - 
  2.1344 -  ///Count the number of connected components of an undirected graph
  2.1345  
  2.1346 -  ///Count the number of connected components of an undirected graph
  2.1347 +  /// \ingroup topology
  2.1348    ///
  2.1349 -  ///\param g The graph. In must be undirected.
  2.1350 -  ///\return The number of components
  2.1351 -  template <class UndirGraph>
  2.1352 -  int countConnectedComponents(const UndirGraph &g) {
  2.1353 +  /// \brief Check that the given undirected graph is bipartite.
  2.1354 +  ///
  2.1355 +  /// Check that the given undirected graph is bipartite.
  2.1356 +  /// \param graph The undirected graph.
  2.1357 +  /// \return %True when the nodes can be separated into two sets that
  2.1358 +  /// there are not connected nodes in neither sets.
  2.1359 +  template <typename UndirGraph>
  2.1360 +  bool bipartite(const UndirGraph& graph) {
  2.1361      checkConcept<concept::UndirGraph, UndirGraph>();
  2.1362 -    int c = 0;
  2.1363 -    Bfs<UndirGraph> bfs(g);
  2.1364 -    bfs.init();
  2.1365 -    for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
  2.1366 -      if(!bfs.reached(n)) {
  2.1367 -	bfs.addSource(n);
  2.1368 -	bfs.start();
  2.1369 -	++c;
  2.1370 -      }
  2.1371 -    }
  2.1372 -    return c;
  2.1373 -  }
  2.1374 -
  2.1375 -
  2.1376 -  ///Find the connected components of an undirected graph
  2.1377 -
  2.1378 -  ///Find the connected components of an undirected graph
  2.1379 -  ///
  2.1380 -  ///\param g The graph. In must be undirected.
  2.1381 -  ///\retval comp A writable node map. The values will be set from 0 to
  2.1382 -  ///the number of the connected components minus one. Each values of the map
  2.1383 -  ///will be set exactly once, the values of a certain component will be
  2.1384 -  ///set continuously.
  2.1385 -  ///\return The number of components
  2.1386 -  ///\todo Test required
  2.1387 -  template <class UndirGraph, class IntNodeMap>
  2.1388 -  int connectedComponents(const UndirGraph &g, IntNodeMap &comp) {
  2.1389 -    checkConcept<concept::UndirGraph, UndirGraph>();
  2.1390 -    checkConcept<concept::WriteMap<typename UndirGraph::Node, int>, 
  2.1391 -      IntNodeMap>();
  2.1392 -    int c = 0;
  2.1393 -    Bfs<UndirGraph> bfs(g);
  2.1394 -    bfs.init();
  2.1395 -    for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
  2.1396 -      if(!bfs.reached(n)) {
  2.1397 -	bfs.addSource(n);
  2.1398 -	while (!bfs.emptyQueue()) {
  2.1399 -	  comp[bfs.nextNode()] = c;
  2.1400 -	  bfs.processNextNode();
  2.1401 -	}
  2.1402 -	++c;
  2.1403 -      }
  2.1404 -    }
  2.1405 -    return c;
  2.1406 -  }
  2.1407 -
  2.1408 -  namespace _components_bits {
  2.1409 -
  2.1410 -    template <typename Key, typename IntMap>
  2.1411 -    struct FillWriteMap : public MapBase<Key, bool> {
  2.1412 -    public:
  2.1413 -      FillWriteMap(IntMap& _map, int& _comp) 
  2.1414 -	: map(_map), comp(_comp) {}
  2.1415 -      void set(Key key, bool value) {
  2.1416 -	if (value) { map.set(key, comp); }
  2.1417 -      }
  2.1418 -    private:
  2.1419 -      IntMap& map;
  2.1420 -      int& comp;
  2.1421 -    };
  2.1422 -
  2.1423 -    template <typename Key, typename Container = std::vector<Key> >
  2.1424 -    struct BackInserterWriteMap : public MapBase<Key, bool> {
  2.1425 -    public:
  2.1426 -      BackInserterWriteMap(Container& _container) 
  2.1427 -	: container(_container) {}
  2.1428 -      void set(Key key, bool value) {
  2.1429 -	if (value) { container.push_back(key); }
  2.1430 -      }
  2.1431 -    private:
  2.1432 -      Container& container;
  2.1433 -    };
  2.1434 -
  2.1435 -  }
  2.1436 -
  2.1437 -  /// \brief Count the strongly connected components of a directed graph
  2.1438 -  ///
  2.1439 -  /// Count the strongly connected components of a directed graph
  2.1440 -  ///
  2.1441 -  /// \param g The graph.
  2.1442 -  /// \return The number of components
  2.1443 -  template <typename Graph>
  2.1444 -  int countStronglyConnectedComponents(const Graph& graph) {
  2.1445 -    checkConcept<concept::StaticGraph, Graph>();
  2.1446 -
  2.1447 -    using namespace _components_bits;
  2.1448 -
  2.1449 -    typedef typename Graph::Node Node;
  2.1450 -    typedef typename Graph::Edge Edge;
  2.1451 -    typedef typename Graph::NodeIt NodeIt;
  2.1452 -    typedef typename Graph::EdgeIt EdgeIt;
  2.1453 -    
  2.1454 -
  2.1455 -    typename Dfs<Graph>::
  2.1456 -      template DefProcessedMap<BackInserterWriteMap<Node> >::
  2.1457 -      Create dfs(graph);
  2.1458 -
  2.1459 -    std::vector<Node> nodes;
  2.1460 -    BackInserterWriteMap<Node> processed(nodes);
  2.1461 -    dfs.processedMap(processed);
  2.1462 -
  2.1463 +    typedef typename UndirGraph::Node Node;
  2.1464 +    typedef typename UndirGraph::NodeIt NodeIt;
  2.1465 +    typedef typename UndirGraph::Edge Edge;
  2.1466 +    if (NodeIt(graph) == INVALID) return false;
  2.1467 +    Dfs<UndirGraph> dfs(graph);
  2.1468      dfs.init();
  2.1469 +    typename UndirGraph::template NodeMap<bool> red(graph);
  2.1470      for (NodeIt it(graph); it != INVALID; ++it) {
  2.1471        if (!dfs.reached(it)) {
  2.1472  	dfs.addSource(it);
  2.1473 -	dfs.start();
  2.1474 +	red[it] = true;
  2.1475 +	while (!dfs.emptyQueue()) {
  2.1476 +	  Edge edge = dfs.nextEdge();
  2.1477 +	  Node source = graph.source(edge);
  2.1478 +	  Node target = graph.target(edge);
  2.1479 +	  if (dfs.reached(target) && red[source] == red[target]) {
  2.1480 +	    return false;
  2.1481 +	  } else {
  2.1482 +	    red[target] = !red[source];
  2.1483 +	  }
  2.1484 +	  dfs.processNextEdge();
  2.1485 +	}
  2.1486        }
  2.1487      }
  2.1488 -
  2.1489 -    typedef RevGraphAdaptor<const Graph> RGraph;
  2.1490 -
  2.1491 -    RGraph rgraph(graph);
  2.1492 -
  2.1493 -    Dfs<RGraph> rdfs(rgraph);
  2.1494 -
  2.1495 -    int num = 0;
  2.1496 -
  2.1497 -    rdfs.init();
  2.1498 -    for (typename std::vector<Node>::reverse_iterator 
  2.1499 -	   it = nodes.rbegin(); it != nodes.rend(); ++it) {
  2.1500 -      if (!rdfs.reached(*it)) {
  2.1501 -	rdfs.addSource(*it);
  2.1502 -	rdfs.start();
  2.1503 -	++num;
  2.1504 -      }
  2.1505 -    }
  2.1506 -    return num;
  2.1507 +    return true;
  2.1508    }
  2.1509 -
  2.1510 -  /// \brief Find the strongly connected components of a directed graph
  2.1511 -  ///
  2.1512 -  /// Find the strongly connected components of a directed graph
  2.1513 -  ///
  2.1514 -  /// \param g The graph.
  2.1515 -  /// \retval comp A writable node map. The values will be set from 0 to
  2.1516 -  /// the number of the strongly connected components minus one. Each values 
  2.1517 -  /// of the map will be set exactly once, the values of a certain component 
  2.1518 -  /// will be set continuously.
  2.1519 -  /// \return The number of components
  2.1520 -  template <typename Graph, typename IntNodeMap>
  2.1521 -  int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) {
  2.1522 -    checkConcept<concept::StaticGraph, Graph>();
  2.1523 -    checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>();
  2.1524 -
  2.1525 -    using namespace _components_bits;
  2.1526 -
  2.1527 -    typedef typename Graph::Node Node;
  2.1528 -    typedef typename Graph::Edge Edge;
  2.1529 -    typedef typename Graph::NodeIt NodeIt;
  2.1530 -    typedef typename Graph::EdgeIt EdgeIt;
  2.1531 -    
  2.1532 -
  2.1533 -    typename Dfs<Graph>::
  2.1534 -      template DefProcessedMap<BackInserterWriteMap<Node> >::
  2.1535 -      Create dfs(graph);
  2.1536 -
  2.1537 -    std::vector<Node> nodes;
  2.1538 -    BackInserterWriteMap<Node> processed(nodes);
  2.1539 -    dfs.processedMap(processed);
  2.1540 -
  2.1541 -    dfs.init();
  2.1542 -    for (NodeIt it(graph); it != INVALID; ++it) {
  2.1543 -      if (!dfs.reached(it)) {
  2.1544 -	dfs.addSource(it);
  2.1545 -	dfs.start();
  2.1546 -      }
  2.1547 -    }
  2.1548 -
  2.1549 -    typedef RevGraphAdaptor<const Graph> RGraph;
  2.1550 -
  2.1551 -    RGraph rgraph(graph);
  2.1552 -
  2.1553 -    typename Dfs<RGraph>::
  2.1554 -      template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >::
  2.1555 -      Create rdfs(rgraph);
  2.1556 -
  2.1557 -    int num = 0;
  2.1558 -    FillWriteMap<Node, IntNodeMap> rprocessed(comp, num);
  2.1559 -    rdfs.processedMap(rprocessed);
  2.1560 -
  2.1561 -    rdfs.init();
  2.1562 -    for (typename std::vector<Node>::reverse_iterator 
  2.1563 -	   it = nodes.rbegin(); it != nodes.rend(); ++it) {
  2.1564 -      if (!rdfs.reached(*it)) {
  2.1565 -	rdfs.addSource(*it);
  2.1566 -	rdfs.start();
  2.1567 -	++num;
  2.1568 -      }
  2.1569 -    }
  2.1570 -    return num;
  2.1571 -  }
  2.1572 -
  2.1573 +   
  2.1574  } //namespace lemon
  2.1575  
  2.1576  #endif //LEMON_TOPOLOGY_H