deba@1698: /* -*- C++ -*-
deba@1698:  * lemon/topology.h - Part of LEMON, a generic C++ optimization library
deba@1698:  *
deba@1698:  * Copyright (C) 2005 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>
deba@1698: #include <lemon/concept/undir_graph.h>
deba@1698: #include <lemon/concept_check.h>
deba@1698: 
deba@1750: #include <lemon/bin_heap.h>
deba@1750: #include <lemon/linear_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.
deba@1750:   /// \warning The empty graph is not connected.
deba@1750:   template <typename UndirGraph>
deba@1750:   bool connected(const UndirGraph& graph) {
deba@1750:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1750:     if (NodeIt(graph) == INVALID) return false;
deba@1750:     Dfs<UndirGraph> 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@1750:   /// \param g The graph. In must be undirected.
deba@1750:   /// \return The number of components
deba@1750:   template <typename UndirGraph>
deba@1750:   int countConnectedComponents(const UndirGraph &graph) {
deba@1750:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750:     typedef typename UndirGraph::Node Node;
deba@1750:     typedef typename UndirGraph::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;
deba@1750:     typename Bfs<UndirGraph>::
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();
deba@1750:     for(typename UndirGraph::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@1750:   /// \param g The graph. In must be undirected.
deba@1750:   /// \retval comp 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:   ///
deba@1750:   template <class UndirGraph, class NodeMap>
deba@1750:   int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {
deba@1750:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750:     typedef typename UndirGraph::Node Node;
deba@1750:     typedef typename UndirGraph::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;
deba@1750:     typename Bfs<UndirGraph>::
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();
deba@1750:     for(typename UndirGraph::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
deba@1750:   /// connected with directed pathes in both direction.
deba@1750:   /// \return %False when the graph is not strongly connected.
deba@1750:   /// \see connected
deba@1750:   ///
deba@1750:   /// \waning Empty graph is not strongly connected.
deba@1750:   template <typename Graph>
deba@1750:   bool stronglyConnected(const Graph& graph) {
deba@1750:     checkConcept<concept::StaticGraph, Graph>();
deba@1750:     if (NodeIt(graph) == INVALID) return false;
deba@1750: 
deba@1750:     typedef typename Graph::Node Node;
deba@1750:     typedef typename Graph::NodeIt NodeIt;
deba@1750: 
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@1750:   /// \param g The graph.
deba@1750:   /// \return The number of 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@1750:   /// \param g The graph.
deba@1750:   /// \retval comp 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@1750:   /// \param g The graph.
deba@1750:   /// \retval comp A writable edge map. The values will be set true when
deba@1750:   /// the edge is cut edge otherwise false.
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@1750:     class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1698:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
deba@1750:       typedef typename Graph::UndirEdge UndirEdge;
deba@1698: 
deba@1750:       CountNodeBiconnectedComponentsVisitor(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@1750:     class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
deba@1750:       typedef typename Graph::UndirEdge UndirEdge;
deba@1750: 
deba@1750:       NodeBiconnectedComponentsVisitor(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;
deba@1750:       std::stack<UndirEdge> _edgeStack;
deba@1750:       int _num;
deba@1750:     };
deba@1750: 
deba@1750: 
deba@1750:     template <typename Graph, typename NodeMap>
deba@1750:     class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
deba@1750:       typedef typename Graph::UndirEdge UndirEdge;
deba@1750: 
deba@1750:       NodeBiconnectedCutNodesVisitor(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;
deba@1750:       std::stack<UndirEdge> _edgeStack;
deba@1750:       int _num;
deba@1750:       bool rootCut;
deba@1750:     };
deba@1750: 
deba@1750:   }
deba@1750: 
deba@1750:   template <typename UndirGraph>
deba@1750:   int countNodeBiconnectedComponents(const UndirGraph& 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.
deba@1750:   template <typename UndirGraph>
deba@1767:   bool biNodeConnected(const UndirGraph& graph) {
deba@1750:     return countNodeBiconnectedComponents(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.
deba@1750:   template <typename UndirGraph>
deba@1750:   int countNodeBiconnectedComponents(const UndirGraph& graph) {
deba@1750:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
deba@1750:     typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;
deba@1750: 
deba@1750:     int compNum = 0;
deba@1750:     Visitor visitor(graph, compNum);
deba@1750: 
deba@1750:     DfsVisit<UndirGraph, 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.
deba@1750:   /// \retval comp A writable undir edge 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:   ///
deba@1750:   template <typename UndirGraph, typename UndirEdgeMap>
deba@1767:   int biNodeConnectedComponents(const UndirGraph& graph, 
deba@1750: 				UndirEdgeMap& compMap) {
deba@1750:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1750:     typedef typename UndirGraph::UndirEdge UndirEdge;
deba@1750:     checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
deba@1750:     typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
deba@1750:     
deba@1750:     int compNum = 0;
deba@1750:     Visitor visitor(graph, compMap, compNum);
deba@1750: 
deba@1750:     DfsVisit<UndirGraph, 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@1750:   /// \retval comp 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.
deba@1750:   template <typename UndirGraph, typename NodeMap>
deba@1767:   int biNodeConnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {
deba@1750:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750:     typedef typename UndirGraph::Node Node;
deba@1750:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1750:     checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
deba@1750:     typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
deba@1750:     
deba@1750:     int cutNum = 0;
deba@1750:     Visitor visitor(graph, cutMap, cutNum);
deba@1750: 
deba@1750:     DfsVisit<UndirGraph, 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@1750:     class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
deba@1750:       typedef typename Graph::UndirEdge UndirEdge;
deba@1750: 
deba@1750:       CountEdgeBiconnectedComponentsVisitor(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@1750:     class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
deba@1750:       typedef typename Graph::UndirEdge UndirEdge;
deba@1750: 
deba@1750:       EdgeBiconnectedComponentsVisitor(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@1750:     class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {
deba@1750:     public:
deba@1750:       typedef typename Graph::Node Node;
deba@1750:       typedef typename Graph::Edge Edge;
deba@1750:       typedef typename Graph::UndirEdge UndirEdge;
deba@1750: 
deba@1750:       EdgeBiconnectedCutEdgesVisitor(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: 
deba@1750:   template <typename UndirGraph>
deba@1750:   int countEdgeBiconnectedComponents(const UndirGraph& 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.
deba@1750:   template <typename UndirGraph>
deba@1767:   bool biEdgeConnected(const UndirGraph& graph) { 
deba@1750:     return countEdgeBiconnectedComponents(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.
deba@1750:   template <typename UndirGraph>
deba@1750:   int countEdgeBiconnectedComponents(const UndirGraph& graph) { 
deba@1750:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
deba@1750:     typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;
deba@1750:     
deba@1750:     int compNum = 0;
deba@1750:     Visitor visitor(graph, compNum);
deba@1750: 
deba@1750:     DfsVisit<UndirGraph, 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@1750:   /// \retval comp 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:   ///
deba@1750:   template <typename UndirGraph, typename NodeMap>
deba@1767:   int biEdgeConnectedComponents(const UndirGraph& graph, NodeMap& compMap) { 
deba@1750:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1750:     typedef typename UndirGraph::Node Node;
deba@1750:     checkConcept<concept::WriteMap<Node, int>, NodeMap>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
deba@1750:     typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
deba@1750:     
deba@1750:     int compNum = 0;
deba@1750:     Visitor visitor(graph, compMap, compNum);
deba@1750: 
deba@1750:     DfsVisit<UndirGraph, 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@1750:   /// \retval comp 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.
deba@1750:   template <typename UndirGraph, typename UndirEdgeMap>
deba@1767:   int biEdgeConnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { 
deba@1750:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1750:     typedef typename UndirGraph::UndirEdge UndirEdge;
deba@1750:     checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>();
deba@1750: 
deba@1750:     using namespace _topology_bits;
deba@1750: 
deba@1750:     typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
deba@1750:     
deba@1750:     int cutNum = 0;
deba@1750:     Visitor visitor(graph, cutMap, cutNum);
deba@1750: 
deba@1750:     DfsVisit<UndirGraph, 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@1750:   /// \param g The graph. In must be directed and acyclic.
deba@1750:   /// \retval comp 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@1750:   /// \param g The graph. In must 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
deba@1698:   template <typename UndirGraph>
deba@1698:   bool acyclic(const UndirGraph& graph) {
deba@1698:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1698:     typedef typename UndirGraph::Node Node;
deba@1698:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1698:     typedef typename UndirGraph::Edge Edge;
deba@1698:     Dfs<UndirGraph> 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.
deba@1698:   template <typename UndirGraph>
deba@1698:   bool tree(const UndirGraph& graph) {
deba@1698:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1698:     typedef typename UndirGraph::Node Node;
deba@1698:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1698:     typedef typename UndirGraph::Edge Edge;
deba@1698:     Dfs<UndirGraph> 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@1750:   /// \brief Check that the given undirected graph is bipartite.
deba@1750:   ///
deba@1750:   /// Check that the given undirected graph is bipartite.
deba@1750:   /// \param graph The undirected graph.
deba@1750:   /// \return %True when the nodes can be separated into two sets that
deba@1750:   /// there are not connected nodes in neither sets.
deba@1750:   template <typename UndirGraph>
deba@1750:   bool bipartite(const UndirGraph& graph) {
deba@1740:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1750:     typedef typename UndirGraph::Node Node;
deba@1750:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1750:     typedef typename UndirGraph::Edge Edge;
deba@1750:     if (NodeIt(graph) == INVALID) return false;
deba@1750:     Dfs<UndirGraph> dfs(graph);
deba@1740:     dfs.init();
deba@1750:     typename UndirGraph::template NodeMap<bool> red(graph);
deba@1740:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1740:       if (!dfs.reached(it)) {
deba@1740: 	dfs.addSource(it);
deba@1750: 	red[it] = true;
deba@1750: 	while (!dfs.emptyQueue()) {
deba@1750: 	  Edge edge = dfs.nextEdge();
deba@1750: 	  Node source = graph.source(edge);
deba@1750: 	  Node target = graph.target(edge);
deba@1750: 	  if (dfs.reached(target) && red[source] == red[target]) {
deba@1750: 	    return false;
deba@1750: 	  } else {
deba@1750: 	    red[target] = !red[source];
deba@1750: 	  }
deba@1750: 	  dfs.processNextEdge();
deba@1750: 	}
deba@1740:       }
deba@1740:     }
deba@1750:     return true;
deba@1740:   }
deba@1750:    
deba@1698: } //namespace lemon
deba@1698: 
deba@1698: #endif //LEMON_TOPOLOGY_H