deba@1698: /* -*- C++ -*-
deba@1698:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1698:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1698:  *
deba@1698:  * Permission to use, modify and distribute this software is granted
deba@1698:  * provided that this copyright notice appears in all copies. For
deba@1698:  * precise terms see the accompanying LICENSE file.
deba@1698:  *
deba@1698:  * This software is provided "AS IS" with no warranty of any kind,
deba@1698:  * express or implied, and with no claim as to its suitability for any
deba@1698:  * purpose.
deba@1698:  *
deba@1698:  */
deba@1698: 
deba@1698: #ifndef LEMON_TOPOLOGY_H
deba@1698: #define LEMON_TOPOLOGY_H
deba@1698: 
deba@1698: #include <lemon/dfs.h>
deba@1740: #include <lemon/bfs.h>
deba@1698: #include <lemon/graph_utils.h>
deba@1750: #include <lemon/graph_adaptor.h>
deba@1750: #include <lemon/maps.h>
deba@1698: 
deba@1698: #include <lemon/concept/graph.h>
klao@1909: #include <lemon/concept/ugraph.h>
deba@1698: #include <lemon/concept_check.h>
deba@1698: 
deba@1750: #include <lemon/bin_heap.h>
deba@2038: #include <lemon/bucket_heap.h>
deba@1750: 
deba@1750: #include <stack>
deba@1750: #include <functional>
deba@1750: 
deba@1750: /// \ingroup topology
deba@1698: /// \file
deba@1698: /// \brief Topology related algorithms
deba@1698: ///
deba@1698: /// Topology related algorithms
deba@1698: 
deba@1698: namespace lemon {
deba@1698: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1750:   /// \brief Check that the given undirected graph is connected.
deba@1750:   ///
deba@1750:   /// Check that the given undirected graph connected.
deba@1750:   /// \param graph The undirected graph.
deba@1750:   /// \return %True when there is path between any two nodes in the graph.
alpar@1807:   /// \note By definition, the empty graph is connected.
klao@1909:   template <typename UGraph>
klao@1909:   bool connected(const UGraph& graph) {
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
alpar@1807:     if (NodeIt(graph) == INVALID) return true;
klao@1909:     Dfs<UGraph> dfs(graph);
deba@1750:     dfs.run(NodeIt(graph));
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	return false;
deba@1750:       }
deba@1750:     }
deba@1750:     return true;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1750:   /// \brief Count the number of connected components of an undirected graph
deba@1750:   ///
deba@1750:   /// Count the number of connected components of an undirected graph
deba@1750:   ///
deba@1793:   /// \param graph The graph. It should be undirected.
deba@1750:   /// \return The number of components
alpar@1807:   /// \note By definition, the empty graph consists
alpar@1807:   /// of zero connected components.
klao@1909:   template <typename UGraph>
klao@1909:   int countConnectedComponents(const UGraph &graph) {
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::Node Node;
klao@1909:     typedef typename UGraph::Edge Edge;
deba@1750: 
deba@1750:     typedef NullMap<Node, Edge> PredMap;
deba@1750:     typedef NullMap<Node, int> DistMap;
deba@1750: 
deba@1750:     int compNum = 0;
klao@1909:     typename Bfs<UGraph>::
deba@1750:       template DefPredMap<PredMap>::
deba@1750:       template DefDistMap<DistMap>::
deba@1750:       Create bfs(graph);
deba@1750: 
deba@1750:     PredMap predMap;
deba@1750:     bfs.predMap(predMap);
deba@1750: 
deba@1750:     DistMap distMap;
deba@1750:     bfs.distMap(distMap);
deba@1750: 
deba@1750:     bfs.init();
klao@1909:     for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@1750:       if (!bfs.reached(n)) {
deba@1750: 	bfs.addSource(n);
deba@1750: 	bfs.start();
deba@1750: 	++compNum;
deba@1750:       }
deba@1750:     }
deba@1750:     return compNum;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1750:   /// \brief Find the connected components of an undirected graph
deba@1750:   ///
deba@1750:   /// Find the connected components of an undirected graph.
deba@1750:   ///
deba@1763:   /// \image html connected_components.png
deba@1763:   /// \image latex connected_components.eps "Connected components" width=\textwidth
deba@1763:   ///
deba@1793:   /// \param graph The graph. It should be undirected.
deba@1793:   /// \retval compMap A writable node map. The values will be set from 0 to
deba@1750:   /// the number of the connected components minus one. Each values of the map
deba@1750:   /// will be set exactly once, the values of a certain component will be
deba@1750:   /// set continuously.
deba@1750:   /// \return The number of components
deba@1763:   ///
klao@1909:   template <class UGraph, class NodeMap>
klao@1909:   int connectedComponents(const UGraph &graph, NodeMap &compMap) {
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::Node Node;
klao@1909:     typedef typename UGraph::Edge Edge;
deba@1750:     checkConcept<concept::WriteMap<Node, int>, NodeMap>();
deba@1750: 
deba@1750:     typedef NullMap<Node, Edge> PredMap;
deba@1750:     typedef NullMap<Node, int> DistMap;
deba@1750: 
deba@1750:     int compNum = 0;
klao@1909:     typename Bfs<UGraph>::
deba@1750:       template DefPredMap<PredMap>::
deba@1750:       template DefDistMap<DistMap>::
deba@1750:       Create bfs(graph);
deba@1750: 
deba@1750:     PredMap predMap;
deba@1750:     bfs.predMap(predMap);
deba@1750: 
deba@1750:     DistMap distMap;
deba@1750:     bfs.distMap(distMap);
deba@1750:     
deba@1750:     bfs.init();
klao@1909:     for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@1750:       if(!bfs.reached(n)) {
deba@1750: 	bfs.addSource(n);
deba@1750: 	while (!bfs.emptyQueue()) {
deba@1750: 	  compMap.set(bfs.nextNode(), compNum);
deba@1750: 	  bfs.processNextNode();
deba@1750: 	}
deba@1750: 	++compNum;
deba@1750:       }
deba@1750:     }
deba@1750:     return compNum;
deba@1750:   }
deba@1750: 
deba@1750:   namespace _topology_bits {
deba@1750: 
deba@1750:     template <typename Graph, typename Iterator >
deba@1750:     struct LeaveOrderVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       LeaveOrderVisitor(Iterator it) : _it(it) {}
deba@1750: 
deba@1750:       void leave(const Node& node) {
deba@1750: 	*(_it++) = node;
deba@1750:       }
deba@1750: 
deba@1750:     private:
deba@1750:       Iterator _it;
deba@1750:     };
deba@1750: 
deba@1750:     template <typename Graph, typename Map>
deba@1750:     struct FillMapVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Map::Value Value;
deba@1750: 
deba@1750:       FillMapVisitor(Map& map, Value& value) 
deba@1750: 	: _map(map), _value(value) {}
deba@1750: 
deba@1750:       void reach(const Node& node) {
deba@1750: 	_map.set(node, _value);
deba@1750:       }
deba@1750:     private:
deba@1750:       Map& _map;
deba@1750:       Value& _value;
deba@1750:     };
deba@1750: 
deba@1750:     template <typename Graph, typename EdgeMap>
deba@1750:     struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
deba@1750: 
deba@1750:       StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap, 
deba@1750: 				       int& cutNum) 
deba@1750: 	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 
deba@1750: 	  _compMap(graph), _num(0) {
deba@1750:       }
deba@1750: 
deba@1750:       void stop(const Node&) {
deba@1750: 	++_num;
deba@1750:       }
deba@1750: 
deba@1750:       void reach(const Node& node) {
deba@1750: 	_compMap.set(node, _num);
deba@1750:       }
deba@1750: 
deba@1750:       void examine(const Edge& edge) {
deba@1750:  	if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) {
deba@1750:  	  _cutMap.set(edge, true);
deba@1750:  	  ++_cutNum;
deba@1750:  	}
deba@1750:       }
deba@1750:     private:
deba@1750:       const Graph& _graph;
deba@1750:       EdgeMap& _cutMap;
deba@1750:       int& _cutNum;
deba@1750: 
deba@1750:       typename Graph::template NodeMap<int> _compMap;
deba@1750:       int _num;
deba@1750:     };
deba@1750: 
deba@1750:   }
deba@1750: 
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1750:   /// \brief Check that the given directed graph is strongly connected.
deba@1750:   ///
deba@1750:   /// Check that the given directed graph is strongly connected. The
deba@1750:   /// graph is strongly connected when any two nodes of the graph are
alpar@1817:   /// connected with directed paths in both direction.
deba@1750:   /// \return %False when the graph is not strongly connected.
deba@1750:   /// \see connected
deba@1750:   ///
alpar@1807:   /// \note By definition, the empty graph is strongly connected.
deba@1750:   template <typename Graph>
deba@1750:   bool stronglyConnected(const Graph& graph) {
deba@1750:     checkConcept<concept::StaticGraph, Graph>();
deba@1750: 
deba@1750:     typedef typename Graph::Node Node;
deba@1750:     typedef typename Graph::NodeIt NodeIt;
deba@1750: 
deba@2082:     if (NodeIt(graph) == INVALID) return true;
deba@2082: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
deba@1750:     typedef DfsVisitor<Graph> Visitor;
deba@1750:     Visitor visitor;
deba@1750: 
deba@1750:     DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@1750:     dfs.init();
deba@1750:     dfs.addSource(NodeIt(graph));
deba@1750:     dfs.start();
deba@1750: 
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	return false;
deba@1750:       }
deba@1750:     }
deba@1750: 
deba@1750:     typedef RevGraphAdaptor<const Graph> RGraph;
deba@1750:     RGraph rgraph(graph);
deba@1750: 
deba@1750:     typedef DfsVisitor<Graph> RVisitor;
deba@1750:     RVisitor rvisitor;
deba@1750: 
deba@1750:     DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
deba@1750:     rdfs.init();    
deba@1750:     rdfs.addSource(NodeIt(graph));
deba@1750:     rdfs.start();
deba@1750: 
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!rdfs.reached(it)) {
deba@1750: 	return false;
deba@1750:       }
deba@1750:     }
deba@1750: 
deba@1750:     return true;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1750:   /// \brief Count the strongly connected components of a directed graph
deba@1750:   ///
deba@1750:   /// Count the strongly connected components of a directed graph.
deba@1750:   /// The strongly connected components are the classes of an equivalence
deba@1750:   /// relation on the nodes of the graph. Two nodes are connected with
deba@1750:   /// directed paths in both direction.
deba@1750:   ///
deba@1793:   /// \param graph The graph.
deba@1750:   /// \return The number of components
alpar@1807:   /// \note By definition, the empty graph has zero
alpar@1807:   /// strongly connected components.
deba@1750:   template <typename Graph>
deba@1750:   int countStronglyConnectedComponents(const Graph& graph) {
deba@1750:     checkConcept<concept::StaticGraph, Graph>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
deba@1750:     typedef typename Graph::Node Node;
deba@1750:     typedef typename Graph::Edge Edge;
deba@1750:     typedef typename Graph::NodeIt NodeIt;
deba@1750:     typedef typename Graph::EdgeIt EdgeIt;
deba@1750:     
deba@1750:     typedef std::vector<Node> Container;
deba@1750:     typedef typename Container::iterator Iterator;
deba@1750: 
deba@1750:     Container nodes(countNodes(graph));
deba@1750:     typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
deba@1750:     Visitor visitor(nodes.begin());
deba@1750:       
deba@1750:     DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@1750:     dfs.init();
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	dfs.addSource(it);
deba@1750: 	dfs.start();
deba@1750:       }
deba@1750:     }
deba@1750: 
deba@1750:     typedef typename Container::reverse_iterator RIterator;
deba@1750:     typedef RevGraphAdaptor<const Graph> RGraph;
deba@1750: 
deba@1750:     RGraph rgraph(graph);
deba@1750: 
deba@1750:     typedef DfsVisitor<Graph> RVisitor;
deba@1750:     RVisitor rvisitor;
deba@1750: 
deba@1750:     DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
deba@1750: 
deba@1750:     int compNum = 0;
deba@1750: 
deba@1750:     rdfs.init();
deba@1750:     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@1750:       if (!rdfs.reached(*it)) {
deba@1750: 	rdfs.addSource(*it);
deba@1750: 	rdfs.start();
deba@1750: 	++compNum;
deba@1750:       }
deba@1750:     }
deba@1750:     return compNum;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1750:   /// \brief Find the strongly connected components of a directed graph
deba@1750:   ///
deba@1750:   /// Find the strongly connected components of a directed graph.
deba@1750:   /// The strongly connected components are the classes of an equivalence
deba@1750:   /// relation on the nodes of the graph. Two nodes are in relationship
deba@1750:   /// when there are directed paths between them in both direction.
deba@1750:   ///
deba@1763:   /// \image html strongly_connected_components.png
deba@1763:   /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
deba@1763:   ///
deba@1793:   /// \param graph The graph.
deba@1793:   /// \retval compMap A writable node map. The values will be set from 0 to
deba@1750:   /// the number of the strongly connected components minus one. Each values 
deba@1750:   /// of the map will be set exactly once, the values of a certain component 
deba@1750:   /// will be set continuously.
deba@1750:   /// \return The number of components
deba@1763:   ///
deba@1750:   template <typename Graph, typename NodeMap>
deba@1750:   int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
deba@1750:     checkConcept<concept::StaticGraph, Graph>();
deba@1750:     typedef typename Graph::Node Node;
deba@1750:     typedef typename Graph::NodeIt NodeIt;
deba@1750:     checkConcept<concept::WriteMap<Node, int>, NodeMap>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750:     
deba@1750:     typedef std::vector<Node> Container;
deba@1750:     typedef typename Container::iterator Iterator;
deba@1750: 
deba@1750:     Container nodes(countNodes(graph));
deba@1750:     typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
deba@1750:     Visitor visitor(nodes.begin());
deba@1750:       
deba@1750:     DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@1750:     dfs.init();
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	dfs.addSource(it);
deba@1750: 	dfs.start();
deba@1750:       }
deba@1750:     }
deba@1750: 
deba@1750:     typedef typename Container::reverse_iterator RIterator;
deba@1750:     typedef RevGraphAdaptor<const Graph> RGraph;
deba@1750: 
deba@1750:     RGraph rgraph(graph);
deba@1750: 
deba@1750:     int compNum = 0;
deba@1750: 
deba@1750:     typedef FillMapVisitor<RGraph, NodeMap> RVisitor;
deba@1750:     RVisitor rvisitor(compMap, compNum);
deba@1750: 
deba@1750:     DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
deba@1750: 
deba@1750:     rdfs.init();
deba@1750:     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@1750:       if (!rdfs.reached(*it)) {
deba@1750: 	rdfs.addSource(*it);
deba@1750: 	rdfs.start();
deba@1750: 	++compNum;
deba@1750:       }
deba@1750:     }
deba@1750:     return compNum;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1750:   /// \brief Find the cut edges of the strongly connected components.
deba@1750:   ///
deba@1750:   /// Find the cut edges of the strongly connected components.
deba@1750:   /// The strongly connected components are the classes of an equivalence
deba@1750:   /// relation on the nodes of the graph. Two nodes are in relationship
deba@1750:   /// when there are directed paths between them in both direction.
deba@1750:   /// The strongly connected components are separated by the cut edges.
deba@1750:   ///
deba@1793:   /// \param graph The graph.
deba@1793:   /// \retval cutMap A writable node map. The values will be set true when the
deba@1793:   /// edge is a cut edge.
deba@1750:   ///
deba@1750:   /// \return The number of cut edges
deba@1750:   template <typename Graph, typename EdgeMap>
deba@1750:   int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
deba@1750:     checkConcept<concept::StaticGraph, Graph>();
deba@1750:     typedef typename Graph::Node Node;
deba@1750:     typedef typename Graph::Edge Edge;
deba@1750:     typedef typename Graph::NodeIt NodeIt;
deba@1750:     checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750:     
deba@1750:     typedef std::vector<Node> Container;
deba@1750:     typedef typename Container::iterator Iterator;
deba@1750: 
deba@1750:     Container nodes(countNodes(graph));
deba@1750:     typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
deba@1750:     Visitor visitor(nodes.begin());
deba@1750:       
deba@1750:     DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@1750:     dfs.init();
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	dfs.addSource(it);
deba@1750: 	dfs.start();
deba@1750:       }
deba@1750:     }
deba@1750: 
deba@1750:     typedef typename Container::reverse_iterator RIterator;
deba@1750:     typedef RevGraphAdaptor<const Graph> RGraph;
deba@1750: 
deba@1750:     RGraph rgraph(graph);
deba@1750: 
deba@1750:     int cutNum = 0;
deba@1750: 
deba@1750:     typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;
deba@1750:     RVisitor rvisitor(rgraph, cutMap, cutNum);
deba@1750: 
deba@1750:     DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
deba@1750: 
deba@1750:     rdfs.init();
deba@1750:     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@1750:       if (!rdfs.reached(*it)) {
deba@1750: 	rdfs.addSource(*it);
deba@1750: 	rdfs.start();
deba@1750:       }
deba@1750:     }
deba@1750:     return cutNum;
deba@1750:   }
deba@1750: 
deba@1698:   namespace _topology_bits {
deba@1698:     
deba@1750:     template <typename Graph>
deba@1800:     class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1698:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
klao@1909:       typedef typename Graph::UEdge UEdge;
deba@1698: 
deba@1800:       CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum) 
deba@1750: 	: _graph(graph), _compNum(compNum), 
deba@1750: 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750: 
deba@1750:       void start(const Node& node) {
deba@1750: 	_predMap.set(node, INVALID);
deba@1750:       }
deba@1750:       
deba@1750:       void reach(const Node& node) {
deba@1750: 	_numMap.set(node, _num);
deba@1750: 	_retMap.set(node, _num);
deba@1750: 	++_num;
deba@1750:       }
deba@1750: 
deba@1750:       void discover(const Edge& edge) {
deba@1750: 	_predMap.set(_graph.target(edge), _graph.source(edge));
deba@1750:       }
deba@1750: 
deba@1750:       void examine(const Edge& edge) {
deba@1750: 	if (_graph.source(edge) == _graph.target(edge) && 
deba@1750: 	    _graph.direction(edge)) {
deba@1750: 	  ++_compNum;
deba@1750: 	  return;
deba@1750: 	}
deba@1750: 	if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
deba@1750: 	  return;
deba@1750: 	}
deba@1750: 	if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
deba@1750: 	  _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
deba@1698: 	}
deba@1698:       }
deba@1698: 
deba@1750:       void backtrack(const Edge& edge) {
deba@1750: 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750: 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750: 	}  
deba@1750: 	if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
deba@1750: 	  ++_compNum;
deba@1750: 	}
deba@1750:       }
deba@1750:       
deba@1750:     private:
deba@1750:       const Graph& _graph;
deba@1750:       int& _compNum; 
deba@1750: 
deba@1750:       typename Graph::template NodeMap<int> _numMap;
deba@1750:       typename Graph::template NodeMap<int> _retMap;
deba@1750:       typename Graph::template NodeMap<Node> _predMap;
deba@1750:       int _num;
deba@1750:     };
deba@1750: 
deba@1750:     template <typename Graph, typename EdgeMap>
deba@1800:     class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
klao@1909:       typedef typename Graph::UEdge UEdge;
deba@1750: 
deba@1800:       BiNodeConnectedComponentsVisitor(const Graph& graph, 
deba@1750: 				       EdgeMap& compMap, int &compNum) 
deba@1750: 	: _graph(graph), _compMap(compMap), _compNum(compNum), 
deba@1750: 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750: 
deba@1750:       void start(const Node& node) {
deba@1750: 	_predMap.set(node, INVALID);
deba@1750:       }
deba@1750:       
deba@1750:       void reach(const Node& node) {
deba@1750: 	_numMap.set(node, _num);
deba@1750: 	_retMap.set(node, _num);
deba@1750: 	++_num;
deba@1750:       }
deba@1750: 
deba@1750:       void discover(const Edge& edge) {
deba@1750: 	Node target = _graph.target(edge);
deba@1750: 	_predMap.set(target, edge);
deba@1750: 	_edgeStack.push(edge);
deba@1750:       }
deba@1750: 
deba@1750:       void examine(const Edge& edge) {
deba@1750: 	Node source = _graph.source(edge);
deba@1750: 	Node target = _graph.target(edge);
deba@1750: 	if (source == target && _graph.direction(edge)) {
deba@1750: 	  _compMap.set(edge, _compNum);
deba@1750: 	  ++_compNum;
deba@1750: 	  return;
deba@1750: 	}
deba@1750: 	if (_numMap[target] < _numMap[source]) {
deba@1750: 	  if (_predMap[source] != _graph.oppositeEdge(edge)) {
deba@1750: 	    _edgeStack.push(edge);
deba@1750: 	  }
deba@1750: 	}
deba@1750: 	if (_predMap[source] != INVALID && 
deba@1750: 	    target == _graph.source(_predMap[source])) {
deba@1750: 	  return;
deba@1750: 	}
deba@1750: 	if (_retMap[source] > _numMap[target]) {
deba@1750: 	  _retMap.set(source, _numMap[target]);
deba@1750: 	}
deba@1750:       }
deba@1750: 
deba@1750:       void backtrack(const Edge& edge) {
deba@1750: 	Node source = _graph.source(edge);
deba@1750: 	Node target = _graph.target(edge);
deba@1750: 	if (_retMap[source] > _retMap[target]) {
deba@1750: 	  _retMap.set(source, _retMap[target]);
deba@1750: 	}  
deba@1750: 	if (_numMap[source] <= _retMap[target]) {
deba@1750: 	  while (_edgeStack.top() != edge) {
deba@1750: 	    _compMap.set(_edgeStack.top(), _compNum);
deba@1750: 	    _edgeStack.pop();
deba@1750: 	  }
deba@1750: 	  _compMap.set(edge, _compNum);
deba@1750: 	  _edgeStack.pop();
deba@1750: 	  ++_compNum;
deba@1750: 	}
deba@1750:       }
deba@1750:       
deba@1750:     private:
deba@1750:       const Graph& _graph;
deba@1750:       EdgeMap& _compMap;
deba@1750:       int& _compNum; 
deba@1750: 
deba@1750:       typename Graph::template NodeMap<int> _numMap;
deba@1750:       typename Graph::template NodeMap<int> _retMap;
deba@1750:       typename Graph::template NodeMap<Edge> _predMap;
klao@1909:       std::stack<UEdge> _edgeStack;
deba@1750:       int _num;
deba@1750:     };
deba@1750: 
deba@1750: 
deba@1750:     template <typename Graph, typename NodeMap>
deba@1800:     class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
klao@1909:       typedef typename Graph::UEdge UEdge;
deba@1750: 
deba@1800:       BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
deba@1750: 				     int& cutNum) 
deba@1750: 	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
deba@1750: 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750: 
deba@1750:       void start(const Node& node) {
deba@1750: 	_predMap.set(node, INVALID);
deba@1750: 	rootCut = false;
deba@1750:       }
deba@1750:       
deba@1750:       void reach(const Node& node) {
deba@1750: 	_numMap.set(node, _num);
deba@1750: 	_retMap.set(node, _num);
deba@1750: 	++_num;
deba@1750:       }
deba@1750: 
deba@1750:       void discover(const Edge& edge) {
deba@1750: 	_predMap.set(_graph.target(edge), _graph.source(edge));
deba@1750:       }
deba@1750: 
deba@1750:       void examine(const Edge& edge) {
deba@1750: 	if (_graph.source(edge) == _graph.target(edge) && 
deba@1750: 	    _graph.direction(edge)) {
deba@1750: 	  if (!_cutMap[_graph.source(edge)]) {
deba@1750: 	    _cutMap.set(_graph.source(edge), true);
deba@1750: 	    ++_cutNum;
deba@1750: 	  }
deba@1750: 	  return;
deba@1750: 	}
deba@1750: 	if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
deba@1750: 	if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
deba@1750: 	  _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
deba@1750: 	}
deba@1750:       }
deba@1750: 
deba@1750:       void backtrack(const Edge& edge) {
deba@1750: 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750: 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750: 	}  
deba@1750: 	if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
deba@1750: 	  if (_predMap[_graph.source(edge)] != INVALID) {
deba@1750: 	    if (!_cutMap[_graph.source(edge)]) {
deba@1750: 	      _cutMap.set(_graph.source(edge), true);
deba@1750: 	      ++_cutNum;
deba@1750: 	    }
deba@1750: 	  } else if (rootCut) {
deba@1750: 	    if (!_cutMap[_graph.source(edge)]) {
deba@1750: 	      _cutMap.set(_graph.source(edge), true);
deba@1750: 	      ++_cutNum;
deba@1750: 	    }
deba@1750: 	  } else {
deba@1750: 	    rootCut = true;
deba@1750: 	  }
deba@1750: 	}
deba@1750:       }
deba@1750:       
deba@1750:     private:
deba@1750:       const Graph& _graph;
deba@1750:       NodeMap& _cutMap;
deba@1750:       int& _cutNum; 
deba@1750: 
deba@1750:       typename Graph::template NodeMap<int> _numMap;
deba@1750:       typename Graph::template NodeMap<int> _retMap;
deba@1750:       typename Graph::template NodeMap<Node> _predMap;
klao@1909:       std::stack<UEdge> _edgeStack;
deba@1750:       int _num;
deba@1750:       bool rootCut;
deba@1750:     };
deba@1750: 
deba@1750:   }
deba@1750: 
klao@1909:   template <typename UGraph>
klao@1909:   int countBiNodeConnectedComponents(const UGraph& graph);
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1767:   /// \brief Checks the graph is bi-node-connected.
deba@1750:   ///
deba@1767:   /// This function checks that the undirected graph is bi-node-connected  
deba@1767:   /// graph. The graph is bi-node-connected if any two undirected edge is 
deba@1750:   /// on same circle.
deba@1750:   ///
deba@1750:   /// \param graph The graph.
deba@1767:   /// \return %True when the graph bi-node-connected.
deba@1750:   /// \todo Make it faster.
klao@1909:   template <typename UGraph>
klao@1909:   bool biNodeConnected(const UGraph& graph) {
deba@1800:     return countBiNodeConnectedComponents(graph) == 1;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1750:   /// \brief Count the biconnected components.
deba@1750:   ///
deba@1767:   /// This function finds the bi-node-connected components in an undirected 
deba@1750:   /// graph. The biconnected components are the classes of an equivalence 
deba@1750:   /// relation on the undirected edges. Two undirected edge is in relationship
deba@1750:   /// when they are on same circle.
deba@1750:   ///
deba@1750:   /// \param graph The graph.
deba@1750:   /// \return The number of components.
klao@1909:   template <typename UGraph>
klao@1909:   int countBiNodeConnectedComponents(const UGraph& graph) {
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
klao@1909:     typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor;
deba@1750: 
deba@1750:     int compNum = 0;
deba@1750:     Visitor visitor(graph, compNum);
deba@1750: 
klao@1909:     DfsVisit<UGraph, Visitor> dfs(graph, visitor);
deba@1750:     dfs.init();
deba@1750:     
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	dfs.addSource(it);
deba@1750: 	dfs.start();
deba@1750:       }
deba@1750:     }
deba@1750:     return compNum;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1767:   /// \brief Find the bi-node-connected components.
deba@1750:   ///
deba@1767:   /// This function finds the bi-node-connected components in an undirected 
deba@1767:   /// graph. The bi-node-connected components are the classes of an equivalence
deba@1750:   /// relation on the undirected edges. Two undirected edge are in relationship
deba@1750:   /// when they are on same circle.
deba@1750:   ///
deba@1763:   /// \image html node_biconnected_components.png
deba@1767:   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
deba@1763:   ///
deba@1750:   /// \param graph The graph.
klao@1909:   /// \retval compMap A writable uedge map. The values will be set from 0
deba@1793:   /// to the number of the biconnected components minus one. Each values 
deba@1750:   /// of the map will be set exactly once, the values of a certain component 
deba@1750:   /// will be set continuously.
deba@1750:   /// \return The number of components.
deba@1763:   ///
klao@1909:   template <typename UGraph, typename UEdgeMap>
klao@1909:   int biNodeConnectedComponents(const UGraph& graph, 
klao@1909: 				UEdgeMap& compMap) {
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
klao@1909:     typedef typename UGraph::UEdge UEdge;
klao@1909:     checkConcept<concept::WriteMap<UEdge, int>, UEdgeMap>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
klao@1909:     typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor;
deba@1750:     
deba@1750:     int compNum = 0;
deba@1750:     Visitor visitor(graph, compMap, compNum);
deba@1750: 
klao@1909:     DfsVisit<UGraph, Visitor> dfs(graph, visitor);
deba@1750:     dfs.init();
deba@1750:     
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	dfs.addSource(it);
deba@1750: 	dfs.start();
deba@1750:       }
deba@1750:     }
deba@1750:     return compNum;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1767:   /// \brief Find the bi-node-connected cut nodes.
deba@1750:   ///
deba@1767:   /// This function finds the bi-node-connected cut nodes in an undirected 
deba@1767:   /// graph. The bi-node-connected components are the classes of an equivalence
deba@1750:   /// relation on the undirected edges. Two undirected edges are in 
deba@1750:   /// relationship when they are on same circle. The biconnected components 
deba@1750:   /// are separted by nodes which are the cut nodes of the components.
deba@1750:   ///
deba@1750:   /// \param graph The graph.
deba@1793:   /// \retval cutMap A writable edge map. The values will be set true when
deba@1750:   /// the node separate two or more components.
deba@1750:   /// \return The number of the cut nodes.
klao@1909:   template <typename UGraph, typename NodeMap>
klao@1909:   int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) {
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::Node Node;
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
deba@1750:     checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
klao@1909:     typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor;
deba@1750:     
deba@1750:     int cutNum = 0;
deba@1750:     Visitor visitor(graph, cutMap, cutNum);
deba@1750: 
klao@1909:     DfsVisit<UGraph, Visitor> dfs(graph, visitor);
deba@1750:     dfs.init();
deba@1750:     
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	dfs.addSource(it);
deba@1750: 	dfs.start();
deba@1750:       }
deba@1750:     }
deba@1750:     return cutNum;
deba@1750:   }
deba@1750: 
deba@1750:   namespace _topology_bits {
deba@1750:     
deba@1750:     template <typename Graph>
deba@1800:     class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
klao@1909:       typedef typename Graph::UEdge UEdge;
deba@1750: 
deba@1800:       CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum) 
deba@1750: 	: _graph(graph), _compNum(compNum), 
deba@1750: 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750: 
deba@1750:       void start(const Node& node) {
deba@1750: 	_predMap.set(node, INVALID);
deba@1750:       }
deba@1750:       
deba@1750:       void reach(const Node& node) {
deba@1750: 	_numMap.set(node, _num);
deba@1750: 	_retMap.set(node, _num);
deba@1750: 	++_num;
deba@1750:       }
deba@1750:       
deba@1750:       void leave(const Node& node) {
deba@1750: 	if (_numMap[node] <= _retMap[node]) {
deba@1750: 	  ++_compNum;
deba@1750: 	}	
deba@1750:       }
deba@1750: 
deba@1750:       void discover(const Edge& edge) {
deba@1750: 	_predMap.set(_graph.target(edge), edge);
deba@1750:       }
deba@1750: 
deba@1750:       void examine(const Edge& edge) {
deba@1750: 	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
deba@1750: 	  return;
deba@1750: 	}
deba@1750: 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750: 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750: 	}
deba@1750:       }
deba@1750: 
deba@1750:       void backtrack(const Edge& edge) {
deba@1750: 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750: 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750: 	}  
deba@1750:       }
deba@1750:       
deba@1750:     private:
deba@1750:       const Graph& _graph;
deba@1750:       int& _compNum; 
deba@1750: 
deba@1750:       typename Graph::template NodeMap<int> _numMap;
deba@1750:       typename Graph::template NodeMap<int> _retMap;
deba@1750:       typename Graph::template NodeMap<Edge> _predMap;
deba@1750:       int _num;
deba@1750:     };
deba@1750: 
deba@1750:     template <typename Graph, typename NodeMap>
deba@1800:     class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
klao@1909:       typedef typename Graph::UEdge UEdge;
deba@1750: 
deba@1800:       BiEdgeConnectedComponentsVisitor(const Graph& graph, 
deba@1750: 				       NodeMap& compMap, int &compNum) 
deba@1750: 	: _graph(graph), _compMap(compMap), _compNum(compNum), 
deba@1750: 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750: 
deba@1750:       void start(const Node& node) {
deba@1750: 	_predMap.set(node, INVALID);
deba@1750:       }
deba@1750:       
deba@1750:       void reach(const Node& node) {
deba@1750: 	_numMap.set(node, _num);
deba@1750: 	_retMap.set(node, _num);
deba@1750: 	_nodeStack.push(node);
deba@1750: 	++_num;
deba@1750:       }
deba@1750:       
deba@1750:       void leave(const Node& node) {
deba@1750: 	if (_numMap[node] <= _retMap[node]) {
deba@1750: 	  while (_nodeStack.top() != node) {
deba@1750: 	    _compMap.set(_nodeStack.top(), _compNum);
deba@1750: 	    _nodeStack.pop();
deba@1750: 	  }
deba@1750: 	  _compMap.set(node, _compNum);
deba@1750: 	  _nodeStack.pop();
deba@1750: 	  ++_compNum;
deba@1750: 	}	
deba@1750:       }
deba@1750: 
deba@1750:       void discover(const Edge& edge) {
deba@1750: 	_predMap.set(_graph.target(edge), edge);
deba@1750:       }
deba@1750: 
deba@1750:       void examine(const Edge& edge) {
deba@1750: 	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
deba@1750: 	  return;
deba@1750: 	}
deba@1750: 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750: 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750: 	}
deba@1750:       }
deba@1750: 
deba@1750:       void backtrack(const Edge& edge) {
deba@1750: 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750: 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750: 	}  
deba@1750:       }
deba@1750:       
deba@1750:     private:
deba@1750:       const Graph& _graph;
deba@1750:       NodeMap& _compMap;
deba@1750:       int& _compNum; 
deba@1750: 
deba@1750:       typename Graph::template NodeMap<int> _numMap;
deba@1750:       typename Graph::template NodeMap<int> _retMap;
deba@1750:       typename Graph::template NodeMap<Edge> _predMap;
deba@1750:       std::stack<Node> _nodeStack;
deba@1750:       int _num;
deba@1750:     };
deba@1750: 
deba@1750: 
deba@1750:     template <typename Graph, typename EdgeMap>
deba@1800:     class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
klao@1909:       typedef typename Graph::UEdge UEdge;
deba@1750: 
deba@1800:       BiEdgeConnectedCutEdgesVisitor(const Graph& graph, 
deba@1750: 				     EdgeMap& cutMap, int &cutNum) 
deba@1750: 	: _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 
deba@1750: 	  _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
deba@1750: 
deba@1750:       void start(const Node& node) {
deba@1750: 	_predMap[node] = INVALID;
deba@1750:       }
deba@1750:       
deba@1750:       void reach(const Node& node) {
deba@1750: 	_numMap.set(node, _num);
deba@1750: 	_retMap.set(node, _num);
deba@1750: 	++_num;
deba@1750:       }
deba@1750:       
deba@1750:       void leave(const Node& node) {
deba@1750: 	if (_numMap[node] <= _retMap[node]) {
deba@1750: 	  if (_predMap[node] != INVALID) {
deba@1750: 	    _cutMap.set(_predMap[node], true);
deba@1750: 	    ++_cutNum;
deba@1750: 	  }
deba@1750: 	}	
deba@1750:       }
deba@1750: 
deba@1750:       void discover(const Edge& edge) {
deba@1750: 	_predMap.set(_graph.target(edge), edge);
deba@1750:       }
deba@1750: 
deba@1750:       void examine(const Edge& edge) {
deba@1750: 	if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
deba@1750: 	  return;
deba@1750: 	}
deba@1750: 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750: 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750: 	}
deba@1750:       }
deba@1750: 
deba@1750:       void backtrack(const Edge& edge) {
deba@1750: 	if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
deba@1750: 	  _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
deba@1750: 	}  
deba@1750:       }
deba@1750:       
deba@1750:     private:
deba@1750:       const Graph& _graph;
deba@1750:       EdgeMap& _cutMap;
deba@1750:       int& _cutNum; 
deba@1750: 
deba@1750:       typename Graph::template NodeMap<int> _numMap;
deba@1750:       typename Graph::template NodeMap<int> _retMap;
deba@1750:       typename Graph::template NodeMap<Edge> _predMap;
deba@1750:       int _num;
deba@1750:     };
deba@1750:   }
deba@1750: 
klao@1909:   template <typename UGraph>
klao@1909:   int countbiEdgeConnectedComponents(const UGraph& graph);
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1767:   /// \brief Checks that the graph is bi-edge-connected.
deba@1750:   ///
deba@1767:   /// This function checks that the graph is bi-edge-connected. The undirected
deba@1767:   /// graph is bi-edge-connected when any two nodes are connected with two
deba@1750:   /// edge-disjoint paths.
deba@1750:   ///
deba@1750:   /// \param graph The undirected graph.
deba@1750:   /// \return The number of components.
deba@1750:   /// \todo Make it faster.
klao@1909:   template <typename UGraph>
klao@1909:   bool biEdgeConnected(const UGraph& graph) { 
deba@1800:     return countBiEdgeConnectedComponents(graph) == 1;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1767:   /// \brief Count the bi-edge-connected components.
deba@1750:   ///
deba@1767:   /// This function count the bi-edge-connected components in an undirected 
deba@1767:   /// graph. The bi-edge-connected components are the classes of an equivalence
deba@1750:   /// relation on the nodes. Two nodes are in relationship when they are  
deba@1750:   /// connected with at least two edge-disjoint paths.
deba@1750:   ///
deba@1750:   /// \param graph The undirected graph.
deba@1750:   /// \return The number of components.
klao@1909:   template <typename UGraph>
klao@1909:   int countBiEdgeConnectedComponents(const UGraph& graph) { 
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
klao@1909:     typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor;
deba@1750:     
deba@1750:     int compNum = 0;
deba@1750:     Visitor visitor(graph, compNum);
deba@1750: 
klao@1909:     DfsVisit<UGraph, Visitor> dfs(graph, visitor);
deba@1750:     dfs.init();
deba@1750:     
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	dfs.addSource(it);
deba@1750: 	dfs.start();
deba@1750:       }
deba@1750:     }
deba@1750:     return compNum;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1767:   /// \brief Find the bi-edge-connected components.
deba@1750:   ///
deba@1767:   /// This function finds the bi-edge-connected components in an undirected 
deba@1767:   /// graph. The bi-edge-connected components are the classes of an equivalence
deba@1750:   /// relation on the nodes. Two nodes are in relationship when they are  
deba@1750:   /// connected at least two edge-disjoint paths.
deba@1750:   ///
deba@1763:   /// \image html edge_biconnected_components.png
deba@1767:   /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
deba@1763:   ///
deba@1750:   /// \param graph The graph.
deba@1793:   /// \retval compMap A writable node map. The values will be set from 0 to
deba@1750:   /// the number of the biconnected components minus one. Each values 
deba@1750:   /// of the map will be set exactly once, the values of a certain component 
deba@1750:   /// will be set continuously.
deba@1750:   /// \return The number of components.
deba@1763:   ///
klao@1909:   template <typename UGraph, typename NodeMap>
klao@1909:   int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) { 
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
klao@1909:     typedef typename UGraph::Node Node;
deba@1750:     checkConcept<concept::WriteMap<Node, int>, NodeMap>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
klao@1909:     typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor;
deba@1750:     
deba@1750:     int compNum = 0;
deba@1750:     Visitor visitor(graph, compMap, compNum);
deba@1750: 
klao@1909:     DfsVisit<UGraph, Visitor> dfs(graph, visitor);
deba@1750:     dfs.init();
deba@1750:     
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	dfs.addSource(it);
deba@1750: 	dfs.start();
deba@1750:       }
deba@1750:     }
deba@1750:     return compNum;
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1767:   /// \brief Find the bi-edge-connected cut edges.
deba@1750:   ///
deba@1767:   /// This function finds the bi-edge-connected components in an undirected 
deba@1767:   /// graph. The bi-edge-connected components are the classes of an equivalence
deba@1750:   /// relation on the nodes. Two nodes are in relationship when they are 
deba@1767:   /// connected with at least two edge-disjoint paths. The bi-edge-connected 
deba@1750:   /// components are separted by edges which are the cut edges of the 
deba@1750:   /// components.
deba@1750:   ///
deba@1750:   /// \param graph The graph.
deba@1793:   /// \retval cutMap A writable node map. The values will be set true when the
deba@1750:   /// edge is a cut edge.
deba@1750:   /// \return The number of cut edges.
klao@1909:   template <typename UGraph, typename UEdgeMap>
klao@1909:   int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) { 
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
klao@1909:     typedef typename UGraph::UEdge UEdge;
klao@1909:     checkConcept<concept::WriteMap<UEdge, bool>, UEdgeMap>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
klao@1909:     typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor;
deba@1750:     
deba@1750:     int cutNum = 0;
deba@1750:     Visitor visitor(graph, cutMap, cutNum);
deba@1750: 
klao@1909:     DfsVisit<UGraph, Visitor> dfs(graph, visitor);
deba@1750:     dfs.init();
deba@1750:     
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	dfs.addSource(it);
deba@1750: 	dfs.start();
deba@1750:       }
deba@1750:     }
deba@1750:     return cutNum;
deba@1750:   }
deba@1750: 
deba@1750: 
deba@1750:   namespace _topology_bits {
deba@1750:     
deba@1750:     template <typename Graph, typename IntNodeMap>
deba@1750:     class TopologicalSortVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge edge;
deba@1750: 
deba@1750:       TopologicalSortVisitor(IntNodeMap& order, int num) 
deba@1750: 	: _order(order), _num(num) {}
deba@1750:       
deba@1750:       void leave(const Node& node) {
deba@1750: 	_order.set(node, --_num);
deba@1698:       }
deba@1698: 
deba@1698:     private:
deba@1750:       IntNodeMap& _order;
deba@1750:       int _num;
deba@1698:     };
deba@1750:     
deba@1698:   }
deba@1698: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1750:   /// \brief Sort the nodes of a DAG into topolgical order.
deba@1750:   ///
deba@1750:   /// Sort the nodes of a DAG into topolgical order.
deba@1750:   ///
deba@1793:   /// \param graph The graph. It should be directed and acyclic.
deba@1793:   /// \retval order A writable node map. The values will be set from 0 to
deba@1750:   /// the number of the nodes in the graph minus one. Each values of the map
deba@1750:   /// will be set exactly once, the values  will be set descending order.
deba@1750:   ///
deba@1750:   /// \see checkedTopologicalSort
deba@1750:   /// \see dag
deba@1698:   template <typename Graph, typename NodeMap>
deba@1750:   void topologicalSort(const Graph& graph, NodeMap& order) {
deba@1750:     using namespace _topology_bits;
deba@1750: 
deba@1750:     checkConcept<concept::StaticGraph, Graph>();
deba@1750:     checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
deba@1750: 
deba@1750:     typedef typename Graph::Node Node;
deba@1750:     typedef typename Graph::NodeIt NodeIt;
deba@1750:     typedef typename Graph::Edge Edge;
deba@1750: 
deba@1750:     TopologicalSortVisitor<Graph, NodeMap> 
deba@1750:       visitor(order, countNodes(graph)); 
deba@1750: 
deba@1750:     DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
deba@1750:       dfs(graph, visitor);
deba@1750: 
deba@1750:     dfs.init();
deba@1750:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1750:       if (!dfs.reached(it)) {
deba@1750: 	dfs.addSource(it);
deba@1750: 	dfs.start();
deba@1750:       }
deba@1750:     }    
deba@1750:   }
deba@1750: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1750:   /// \brief Sort the nodes of a DAG into topolgical order.
deba@1750:   ///
deba@1750:   /// Sort the nodes of a DAG into topolgical order. It also checks
deba@1750:   /// that the given graph is DAG.
deba@1750:   ///
deba@1793:   /// \param graph The graph. It should be directed and acyclic.
deba@1750:   /// \retval order A readable - writable node map. The values will be set 
deba@1750:   /// from 0 to the number of the nodes in the graph minus one. Each values 
deba@1750:   /// of the map will be set exactly once, the values will be set descending 
deba@1750:   /// order.
deba@1750:   /// \return %False when the graph is not DAG.
deba@1750:   ///
deba@1750:   /// \see topologicalSort
deba@1750:   /// \see dag
deba@1750:   template <typename Graph, typename NodeMap>
deba@1750:   bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
deba@1698:     using namespace _topology_bits;
deba@1698: 
deba@1698:     checkConcept<concept::StaticGraph, Graph>();
deba@1698:     checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
deba@1698: 
deba@1698:     typedef typename Graph::Node Node;
deba@1698:     typedef typename Graph::NodeIt NodeIt;
deba@1698:     typedef typename Graph::Edge Edge;
deba@1698: 
deba@1750:     order = constMap<Node, int, -1>();
deba@1698: 
deba@1750:     TopologicalSortVisitor<Graph, NodeMap> 
deba@1750:       visitor(order, countNodes(graph)); 
deba@1698: 
deba@1750:     DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
deba@1750:       dfs(graph, visitor);
deba@1698: 
deba@1698:     dfs.init();
deba@1698:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698:       if (!dfs.reached(it)) {
deba@1698: 	dfs.addSource(it);
deba@1698: 	while (!dfs.emptyQueue()) {
deba@1750:  	  Edge edge = dfs.nextEdge();
deba@1750:  	  Node target = graph.target(edge);
deba@1750:  	  if (dfs.reached(target) && order[target] == -1) {
deba@1750:  	    return false;
deba@1750:  	  }
deba@1750:  	  dfs.processNextEdge();
deba@1750:  	}
deba@1698:       }
deba@1750:     }
deba@1698:     return true;
deba@1698:   }
deba@1698: 
deba@1750:   /// \ingroup topology
deba@1698:   ///
deba@1750:   /// \brief Check that the given directed graph is a DAG.
deba@1750:   ///
deba@1750:   /// Check that the given directed graph is a DAG. The DAG is
deba@1698:   /// an Directed Acyclic Graph.
deba@1750:   /// \return %False when the graph is not DAG.
deba@1750:   /// \see acyclic
deba@1698:   template <typename Graph>
deba@1698:   bool dag(const Graph& graph) {
deba@1698: 
deba@1698:     checkConcept<concept::StaticGraph, Graph>();
deba@1698: 
deba@1698:     typedef typename Graph::Node Node;
deba@1698:     typedef typename Graph::NodeIt NodeIt;
deba@1698:     typedef typename Graph::Edge Edge;
deba@1698: 
deba@1698:     typedef typename Graph::template NodeMap<bool> ProcessedMap;
deba@1698: 
deba@1698:     typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
deba@1709:       Create dfs(graph);
deba@1698: 
deba@1698:     ProcessedMap processed(graph);
deba@1698:     dfs.processedMap(processed);
deba@1698: 
deba@1698:     dfs.init();
deba@1698:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698:       if (!dfs.reached(it)) {
deba@1698: 	dfs.addSource(it);
deba@1698: 	while (!dfs.emptyQueue()) {
deba@1698: 	  Edge edge = dfs.nextEdge();
deba@1698: 	  Node target = graph.target(edge);
deba@1698: 	  if (dfs.reached(target) && !processed[target]) {
deba@1698: 	    return false;
deba@1698: 	  }
deba@1698: 	  dfs.processNextEdge();
deba@1698: 	}
deba@1698:       }
deba@1698:     }    
deba@1698:     return true;
deba@1698:   }
deba@1698: 
deba@1750:   /// \ingroup topology
deba@1698:   ///
deba@1698:   /// \brief Check that the given undirected graph is acyclic.
deba@1698:   ///
deba@1698:   /// Check that the given undirected graph acyclic.
deba@1750:   /// \param graph The undirected graph.
deba@1750:   /// \return %True when there is no circle in the graph.
deba@1750:   /// \see dag
klao@1909:   template <typename UGraph>
klao@1909:   bool acyclic(const UGraph& graph) {
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::Node Node;
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
klao@1909:     typedef typename UGraph::Edge Edge;
klao@1909:     Dfs<UGraph> dfs(graph);
deba@1698:     dfs.init();
deba@1698:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698:       if (!dfs.reached(it)) {
deba@1698: 	dfs.addSource(it);
deba@1698: 	while (!dfs.emptyQueue()) {
deba@1698: 	  Edge edge = dfs.nextEdge();
deba@1698: 	  Node source = graph.source(edge);
deba@1698: 	  Node target = graph.target(edge);
deba@1698: 	  if (dfs.reached(target) && 
deba@1763: 	      dfs.predEdge(source) != graph.oppositeEdge(edge)) {
deba@1698: 	    return false;
deba@1698: 	  }
deba@1698: 	  dfs.processNextEdge();
deba@1698: 	}
deba@1698:       }
deba@1698:     }
deba@1698:     return true;
deba@1698:   }
deba@1698: 
deba@1750:   /// \ingroup topology
deba@1750:   ///
deba@1698:   /// \brief Check that the given undirected graph is tree.
deba@1698:   ///
deba@1698:   /// Check that the given undirected graph is tree.
deba@1750:   /// \param graph The undirected graph.
deba@1750:   /// \return %True when the graph is acyclic and connected.
klao@1909:   template <typename UGraph>
klao@1909:   bool tree(const UGraph& graph) {
klao@1909:     checkConcept<concept::UGraph, UGraph>();
klao@1909:     typedef typename UGraph::Node Node;
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
klao@1909:     typedef typename UGraph::Edge Edge;
klao@1909:     Dfs<UGraph> dfs(graph);
deba@1698:     dfs.init();
deba@1698:     dfs.addSource(NodeIt(graph));
deba@1698:     while (!dfs.emptyQueue()) {
deba@1698:       Edge edge = dfs.nextEdge();
deba@1698:       Node source = graph.source(edge);
deba@1698:       Node target = graph.target(edge);
deba@1698:       if (dfs.reached(target) && 
deba@1763: 	  dfs.predEdge(source) != graph.oppositeEdge(edge)) {
deba@1698: 	return false;
deba@1698:       }
deba@1698:       dfs.processNextEdge();
deba@1698:     }
deba@1698:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698:       if (!dfs.reached(it)) {
deba@1698: 	return false;
deba@1698:       }
deba@1698:     }    
deba@1698:     return true;
deba@1698:   }
alpar@1739: 
deba@1750:   /// \ingroup topology
alpar@1739:   ///
deba@1800:   /// \brief Check if the given undirected graph is bipartite or not
deba@1750:   ///
deba@1800:   /// The function checks if the given undirected \c graph graph is bipartite 
deba@1800:   /// or not. The \ref Bfs algorithm is used to calculate the result.
deba@1750:   /// \param graph The undirected graph.
deba@1800:   /// \return %True if \c graph is bipartite, %false otherwise.
deba@1800:   /// \sa bipartitePartitions
deba@1800:   ///
deba@1800:   /// \author Balazs Attila Mihaly  
klao@1909:   template<typename UGraph>
klao@1909:   inline bool bipartite(const UGraph &graph){
klao@1909:     checkConcept<concept::UGraph, UGraph>();
deba@1800:     
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
klao@1909:     typedef typename UGraph::EdgeIt EdgeIt;
deba@1800:     
klao@1909:     Bfs<UGraph> bfs(graph);
deba@1800:     bfs.init();
deba@1800:     for(NodeIt i(graph);i!=INVALID;++i){
deba@1800:       if(!bfs.reached(i)){
deba@1800: 	bfs.run(i);
deba@1800:       }
deba@1800:     }
deba@1800:     for(EdgeIt i(graph);i!=INVALID;++i){
deba@1800:       if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
deba@1800:     }
deba@1800:     return true;
deba@1979:   }
deba@1800:   
deba@1800:   /// \ingroup topology
deba@1800:   ///
deba@1800:   /// \brief Check if the given undirected graph is bipartite or not
deba@1800:   ///
deba@1800:   /// The function checks if the given undirected graph is bipartite 
deba@1800:   /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result. 
deba@1800:   /// During the execution, the \c partMap will be set as the two 
deba@1800:   /// partitions of the graph.
deba@1800:   /// \param graph The undirected graph.
alpar@1808:   /// \retval partMap A writable bool map of nodes. It will be set as the
deba@1800:   /// two partitions of the graph. 
deba@1800:   /// \return %True if \c graph is bipartite, %false otherwise.
deba@1800:   ///
deba@1800:   /// \author Balazs Attila Mihaly  
deba@1800:   ///
deba@1800:   /// \image html bipartite_partitions.png
deba@1800:   /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
klao@1909:   template<typename UGraph, typename NodeMap>
klao@1909:   inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
klao@1909:     checkConcept<concept::UGraph, UGraph>();
deba@1800:     
klao@1909:     typedef typename UGraph::Node Node;
klao@1909:     typedef typename UGraph::NodeIt NodeIt;
klao@1909:     typedef typename UGraph::EdgeIt EdgeIt;
deba@1800:   
klao@1909:     Bfs<UGraph> bfs(graph);
deba@1800:     bfs.init();
deba@1800:     for(NodeIt i(graph);i!=INVALID;++i){
deba@1800:       if(!bfs.reached(i)){
deba@1800: 	bfs.addSource(i);
deba@1800: 	for(Node j=bfs.processNextNode();!bfs.emptyQueue();
deba@1800: 	    j=bfs.processNextNode()){
deba@1800: 	  partMap.set(j,bfs.dist(j)%2==0);
deba@1750: 	}
deba@1740:       }
deba@1740:     }
deba@1800:     for(EdgeIt i(graph);i!=INVALID;++i){
deba@1800:       if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
deba@1800:     }
deba@1750:     return true;
deba@1979:   }
deba@1750:    
deba@1698: } //namespace lemon
deba@1698: 
deba@1698: #endif //LEMON_TOPOLOGY_H