deba@417: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@417: * deba@417: * This file is a part of LEMON, a generic C++ optimization library. deba@417: * alpar@761: * Copyright (C) 2003-2011 deba@417: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@417: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@417: * deba@417: * Permission to use, modify and distribute this software is granted deba@417: * provided that this copyright notice appears in all copies. For deba@417: * precise terms see the accompanying LICENSE file. deba@417: * deba@417: * This software is provided "AS IS" with no warranty of any kind, deba@417: * express or implied, and with no claim as to its suitability for any deba@417: * purpose. deba@417: * deba@417: */ deba@417: deba@419: #ifndef LEMON_CONNECTIVITY_H deba@419: #define LEMON_CONNECTIVITY_H deba@417: deba@417: #include deba@417: #include deba@417: #include deba@417: #include deba@417: #include deba@417: deba@417: #include deba@417: #include deba@417: #include deba@417: deba@417: #include deba@417: #include deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// \file deba@417: /// \brief Connectivity algorithms deba@417: /// deba@417: /// Connectivity algorithms deba@417: deba@417: namespace lemon { deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether an undirected graph is connected. deba@417: /// kpeter@646: /// This function checks whether the given undirected graph is connected, kpeter@646: /// i.e. there is a path between any two nodes in the graph. kpeter@646: /// kpeter@646: /// \return \c true if the graph is connected. deba@417: /// \note By definition, the empty graph is connected. kpeter@646: /// kpeter@646: /// \see countConnectedComponents(), connectedComponents() kpeter@646: /// \see stronglyConnected() deba@417: template deba@417: bool connected(const Graph& graph) { deba@417: checkConcept(); deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: if (NodeIt(graph) == INVALID) return true; deba@417: Dfs dfs(graph); deba@417: dfs.run(NodeIt(graph)); deba@417: for (NodeIt it(graph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: return false; deba@417: } deba@417: } deba@417: return true; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// deba@417: /// \brief Count the number of connected components of an undirected graph deba@417: /// kpeter@646: /// This function counts the number of connected components of the given kpeter@646: /// undirected graph. deba@417: /// kpeter@646: /// The connected components are the classes of an equivalence relation kpeter@646: /// on the nodes of an undirected graph. Two nodes are in the same class kpeter@646: /// if they are connected with a path. kpeter@646: /// kpeter@646: /// \return The number of connected components. deba@417: /// \note By definition, the empty graph consists deba@417: /// of zero connected components. kpeter@646: /// kpeter@646: /// \see connected(), connectedComponents() deba@417: template deba@417: int countConnectedComponents(const Graph &graph) { deba@417: checkConcept(); deba@417: typedef typename Graph::Node Node; deba@417: typedef typename Graph::Arc Arc; deba@417: deba@417: typedef NullMap PredMap; deba@417: typedef NullMap DistMap; deba@417: deba@417: int compNum = 0; deba@417: typename Bfs:: deba@417: template SetPredMap:: deba@417: template SetDistMap:: deba@417: Create bfs(graph); deba@417: deba@417: PredMap predMap; deba@417: bfs.predMap(predMap); deba@417: deba@417: DistMap distMap; deba@417: bfs.distMap(distMap); deba@417: deba@417: bfs.init(); deba@417: for(typename Graph::NodeIt n(graph); n != INVALID; ++n) { deba@417: if (!bfs.reached(n)) { deba@417: bfs.addSource(n); deba@417: bfs.start(); deba@417: ++compNum; deba@417: } deba@417: } deba@417: return compNum; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// deba@417: /// \brief Find the connected components of an undirected graph deba@417: /// kpeter@646: /// This function finds the connected components of the given undirected kpeter@646: /// graph. kpeter@646: /// kpeter@646: /// The connected components are the classes of an equivalence relation kpeter@646: /// on the nodes of an undirected graph. Two nodes are in the same class kpeter@646: /// if they are connected with a path. deba@417: /// kpeter@578: /// \image html connected_components.png kpeter@578: /// \image latex connected_components.eps "Connected components" width=\textwidth kpeter@578: /// kpeter@646: /// \param graph The undirected graph. deba@417: /// \retval compMap A writable node map. The values will be set from 0 to kpeter@646: /// the number of the connected components minus one. Each value of the map kpeter@646: /// will be set exactly once, and the values of a certain component will be deba@417: /// set continuously. kpeter@646: /// \return The number of connected components. kpeter@646: /// \note By definition, the empty graph consists kpeter@646: /// of zero connected components. kpeter@646: /// kpeter@646: /// \see connected(), countConnectedComponents() deba@417: template deba@417: int connectedComponents(const Graph &graph, NodeMap &compMap) { deba@417: checkConcept(); deba@417: typedef typename Graph::Node Node; deba@417: typedef typename Graph::Arc Arc; deba@417: checkConcept, NodeMap>(); deba@417: deba@417: typedef NullMap PredMap; deba@417: typedef NullMap DistMap; deba@417: deba@417: int compNum = 0; deba@417: typename Bfs:: deba@417: template SetPredMap:: deba@417: template SetDistMap:: deba@417: Create bfs(graph); deba@417: deba@417: PredMap predMap; deba@417: bfs.predMap(predMap); deba@417: deba@417: DistMap distMap; deba@417: bfs.distMap(distMap); deba@417: deba@417: bfs.init(); deba@417: for(typename Graph::NodeIt n(graph); n != INVALID; ++n) { deba@417: if(!bfs.reached(n)) { deba@417: bfs.addSource(n); deba@417: while (!bfs.emptyQueue()) { deba@417: compMap.set(bfs.nextNode(), compNum); deba@417: bfs.processNextNode(); deba@417: } deba@417: ++compNum; deba@417: } deba@417: } deba@417: return compNum; deba@417: } deba@417: deba@419: namespace _connectivity_bits { deba@417: deba@417: template deba@417: struct LeaveOrderVisitor : public DfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Node Node; deba@417: LeaveOrderVisitor(Iterator it) : _it(it) {} deba@417: deba@417: void leave(const Node& node) { deba@417: *(_it++) = node; deba@417: } deba@417: deba@417: private: deba@417: Iterator _it; deba@417: }; deba@417: deba@417: template deba@417: struct FillMapVisitor : public DfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Map::Value Value; deba@417: deba@417: FillMapVisitor(Map& map, Value& value) deba@417: : _map(map), _value(value) {} deba@417: deba@417: void reach(const Node& node) { deba@417: _map.set(node, _value); deba@417: } deba@417: private: deba@417: Map& _map; deba@417: Value& _value; deba@417: }; deba@417: deba@417: template deba@419: struct StronglyConnectedCutArcsVisitor : public DfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::Arc Arc; deba@417: deba@419: StronglyConnectedCutArcsVisitor(const Digraph& digraph, deba@419: ArcMap& cutMap, deba@419: int& cutNum) deba@417: : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum), deba@419: _compMap(digraph, -1), _num(-1) { deba@417: } deba@417: deba@419: void start(const Node&) { deba@417: ++_num; deba@417: } deba@417: deba@417: void reach(const Node& node) { deba@417: _compMap.set(node, _num); deba@417: } deba@417: deba@417: void examine(const Arc& arc) { deba@417: if (_compMap[_digraph.source(arc)] != deba@417: _compMap[_digraph.target(arc)]) { deba@417: _cutMap.set(arc, true); deba@417: ++_cutNum; deba@417: } deba@417: } deba@417: private: deba@417: const Digraph& _digraph; deba@417: ArcMap& _cutMap; deba@417: int& _cutNum; deba@417: deba@417: typename Digraph::template NodeMap _compMap; deba@417: int _num; deba@417: }; deba@417: deba@417: } deba@417: deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether a directed graph is strongly connected. deba@417: /// kpeter@646: /// This function checks whether the given directed graph is strongly kpeter@646: /// connected, i.e. any two nodes of the digraph are deba@417: /// connected with directed paths in both direction. deba@417: /// kpeter@646: /// \return \c true if the digraph is strongly connected. kpeter@646: /// \note By definition, the empty digraph is strongly connected. alpar@761: /// kpeter@646: /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() kpeter@646: /// \see connected() deba@417: template deba@417: bool stronglyConnected(const Digraph& digraph) { deba@417: checkConcept(); deba@417: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::NodeIt NodeIt; deba@417: deba@417: typename Digraph::Node source = NodeIt(digraph); deba@417: if (source == INVALID) return true; deba@417: deba@419: using namespace _connectivity_bits; deba@417: deba@417: typedef DfsVisitor Visitor; deba@417: Visitor visitor; deba@417: deba@417: DfsVisit dfs(digraph, visitor); deba@417: dfs.init(); deba@417: dfs.addSource(source); deba@417: dfs.start(); deba@417: deba@417: for (NodeIt it(digraph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: return false; deba@417: } deba@417: } deba@417: deba@417: typedef ReverseDigraph RDigraph; deba@419: typedef typename RDigraph::NodeIt RNodeIt; deba@417: RDigraph rdigraph(digraph); deba@417: kpeter@646: typedef DfsVisitor RVisitor; deba@417: RVisitor rvisitor; deba@417: deba@417: DfsVisit rdfs(rdigraph, rvisitor); deba@417: rdfs.init(); deba@417: rdfs.addSource(source); deba@417: rdfs.start(); deba@417: deba@419: for (RNodeIt it(rdigraph); it != INVALID; ++it) { deba@417: if (!rdfs.reached(it)) { deba@417: return false; deba@417: } deba@417: } deba@417: deba@417: return true; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// alpar@761: /// \brief Count the number of strongly connected components of a kpeter@646: /// directed graph deba@417: /// kpeter@646: /// This function counts the number of strongly connected components of kpeter@646: /// the given directed graph. kpeter@646: /// deba@417: /// The strongly connected components are the classes of an kpeter@646: /// equivalence relation on the nodes of a digraph. Two nodes are in deba@417: /// the same class if they are connected with directed paths in both deba@417: /// direction. deba@417: /// kpeter@646: /// \return The number of strongly connected components. kpeter@646: /// \note By definition, the empty digraph has zero deba@417: /// strongly connected components. kpeter@646: /// kpeter@646: /// \see stronglyConnected(), stronglyConnectedComponents() deba@417: template deba@417: int countStronglyConnectedComponents(const Digraph& digraph) { deba@417: checkConcept(); deba@417: deba@419: using namespace _connectivity_bits; deba@417: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::Arc Arc; deba@417: typedef typename Digraph::NodeIt NodeIt; deba@417: typedef typename Digraph::ArcIt ArcIt; deba@417: deba@417: typedef std::vector Container; deba@417: typedef typename Container::iterator Iterator; deba@417: deba@417: Container nodes(countNodes(digraph)); deba@417: typedef LeaveOrderVisitor Visitor; deba@417: Visitor visitor(nodes.begin()); deba@417: deba@417: DfsVisit dfs(digraph, visitor); deba@417: dfs.init(); deba@417: for (NodeIt it(digraph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: dfs.start(); deba@417: } deba@417: } deba@417: deba@417: typedef typename Container::reverse_iterator RIterator; deba@417: typedef ReverseDigraph RDigraph; deba@417: deba@417: RDigraph rdigraph(digraph); deba@417: deba@417: typedef DfsVisitor RVisitor; deba@417: RVisitor rvisitor; deba@417: deba@417: DfsVisit rdfs(rdigraph, rvisitor); deba@417: deba@417: int compNum = 0; deba@417: deba@417: rdfs.init(); deba@417: for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { deba@417: if (!rdfs.reached(*it)) { deba@417: rdfs.addSource(*it); deba@417: rdfs.start(); deba@417: ++compNum; deba@417: } deba@417: } deba@417: return compNum; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// deba@417: /// \brief Find the strongly connected components of a directed graph deba@417: /// kpeter@646: /// This function finds the strongly connected components of the given kpeter@646: /// directed graph. In addition, the numbering of the components will kpeter@646: /// satisfy that there is no arc going from a higher numbered component kpeter@646: /// to a lower one (i.e. it provides a topological order of the components). kpeter@646: /// kpeter@646: /// The strongly connected components are the classes of an kpeter@646: /// equivalence relation on the nodes of a digraph. Two nodes are in kpeter@646: /// the same class if they are connected with directed paths in both kpeter@646: /// direction. deba@417: /// kpeter@578: /// \image html strongly_connected_components.png kpeter@578: /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth kpeter@578: /// deba@417: /// \param digraph The digraph. deba@417: /// \retval compMap A writable node map. The values will be set from 0 to deba@417: /// the number of the strongly connected components minus one. Each value kpeter@646: /// of the map will be set exactly once, and the values of a certain kpeter@646: /// component will be set continuously. kpeter@646: /// \return The number of strongly connected components. kpeter@646: /// \note By definition, the empty digraph has zero kpeter@646: /// strongly connected components. kpeter@646: /// kpeter@646: /// \see stronglyConnected(), countStronglyConnectedComponents() deba@417: template deba@417: int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { deba@417: checkConcept(); deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::NodeIt NodeIt; deba@417: checkConcept, NodeMap>(); deba@417: deba@419: using namespace _connectivity_bits; deba@417: deba@417: typedef std::vector Container; deba@417: typedef typename Container::iterator Iterator; deba@417: deba@417: Container nodes(countNodes(digraph)); deba@417: typedef LeaveOrderVisitor Visitor; deba@417: Visitor visitor(nodes.begin()); deba@417: deba@417: DfsVisit dfs(digraph, visitor); deba@417: dfs.init(); deba@417: for (NodeIt it(digraph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: dfs.start(); deba@417: } deba@417: } deba@417: deba@417: typedef typename Container::reverse_iterator RIterator; deba@417: typedef ReverseDigraph RDigraph; deba@417: deba@417: RDigraph rdigraph(digraph); deba@417: deba@417: int compNum = 0; deba@417: deba@417: typedef FillMapVisitor RVisitor; deba@417: RVisitor rvisitor(compMap, compNum); deba@417: deba@417: DfsVisit rdfs(rdigraph, rvisitor); deba@417: deba@417: rdfs.init(); deba@417: for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { deba@417: if (!rdfs.reached(*it)) { deba@417: rdfs.addSource(*it); deba@417: rdfs.start(); deba@417: ++compNum; deba@417: } deba@417: } deba@417: return compNum; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// deba@417: /// \brief Find the cut arcs of the strongly connected components. deba@417: /// kpeter@646: /// This function finds the cut arcs of the strongly connected components kpeter@646: /// of the given digraph. kpeter@646: /// kpeter@646: /// The strongly connected components are the classes of an kpeter@646: /// equivalence relation on the nodes of a digraph. Two nodes are in kpeter@646: /// the same class if they are connected with directed paths in both kpeter@646: /// direction. deba@417: /// The strongly connected components are separated by the cut arcs. deba@417: /// kpeter@646: /// \param digraph The digraph. kpeter@646: /// \retval cutMap A writable arc map. The values will be set to \c true kpeter@646: /// for the cut arcs (exactly once for each cut arc), and will not be kpeter@646: /// changed for other arcs. kpeter@646: /// \return The number of cut arcs. deba@417: /// kpeter@646: /// \see stronglyConnected(), stronglyConnectedComponents() deba@417: template kpeter@646: int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) { deba@417: checkConcept(); deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::Arc Arc; deba@417: typedef typename Digraph::NodeIt NodeIt; deba@417: checkConcept, ArcMap>(); deba@417: deba@419: using namespace _connectivity_bits; deba@417: deba@417: typedef std::vector Container; deba@417: typedef typename Container::iterator Iterator; deba@417: kpeter@646: Container nodes(countNodes(digraph)); deba@417: typedef LeaveOrderVisitor Visitor; deba@417: Visitor visitor(nodes.begin()); deba@417: kpeter@646: DfsVisit dfs(digraph, visitor); deba@417: dfs.init(); kpeter@646: for (NodeIt it(digraph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: dfs.start(); deba@417: } deba@417: } deba@417: deba@417: typedef typename Container::reverse_iterator RIterator; deba@417: typedef ReverseDigraph RDigraph; deba@417: kpeter@646: RDigraph rdigraph(digraph); deba@417: deba@417: int cutNum = 0; deba@417: deba@419: typedef StronglyConnectedCutArcsVisitor RVisitor; kpeter@646: RVisitor rvisitor(rdigraph, cutMap, cutNum); deba@417: kpeter@646: DfsVisit rdfs(rdigraph, rvisitor); deba@417: deba@417: rdfs.init(); deba@417: for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { deba@417: if (!rdfs.reached(*it)) { deba@417: rdfs.addSource(*it); deba@417: rdfs.start(); deba@417: } deba@417: } deba@417: return cutNum; deba@417: } deba@417: deba@419: namespace _connectivity_bits { deba@417: deba@417: template deba@417: class CountBiNodeConnectedComponentsVisitor : public DfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::Arc Arc; deba@417: typedef typename Digraph::Edge Edge; deba@417: deba@417: CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum) deba@417: : _graph(graph), _compNum(compNum), deba@417: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@417: deba@417: void start(const Node& node) { deba@417: _predMap.set(node, INVALID); deba@417: } deba@417: deba@417: void reach(const Node& node) { deba@417: _numMap.set(node, _num); deba@417: _retMap.set(node, _num); deba@417: ++_num; deba@417: } deba@417: deba@417: void discover(const Arc& edge) { deba@417: _predMap.set(_graph.target(edge), _graph.source(edge)); deba@417: } deba@417: deba@417: void examine(const Arc& edge) { deba@417: if (_graph.source(edge) == _graph.target(edge) && deba@417: _graph.direction(edge)) { deba@417: ++_compNum; deba@417: return; deba@417: } deba@417: if (_predMap[_graph.source(edge)] == _graph.target(edge)) { deba@417: return; deba@417: } deba@417: if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) { deba@417: _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]); deba@417: } deba@417: } deba@417: deba@417: void backtrack(const Arc& edge) { deba@417: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@417: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@417: } deba@417: if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) { deba@417: ++_compNum; deba@417: } deba@417: } deba@417: deba@417: private: deba@417: const Digraph& _graph; deba@417: int& _compNum; deba@417: deba@417: typename Digraph::template NodeMap _numMap; deba@417: typename Digraph::template NodeMap _retMap; deba@417: typename Digraph::template NodeMap _predMap; deba@417: int _num; deba@417: }; deba@417: deba@417: template deba@417: class BiNodeConnectedComponentsVisitor : public DfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::Arc Arc; deba@417: typedef typename Digraph::Edge Edge; deba@417: deba@417: BiNodeConnectedComponentsVisitor(const Digraph& graph, deba@417: ArcMap& compMap, int &compNum) deba@417: : _graph(graph), _compMap(compMap), _compNum(compNum), deba@417: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@417: deba@417: void start(const Node& node) { deba@417: _predMap.set(node, INVALID); deba@417: } deba@417: deba@417: void reach(const Node& node) { deba@417: _numMap.set(node, _num); deba@417: _retMap.set(node, _num); deba@417: ++_num; deba@417: } deba@417: deba@417: void discover(const Arc& edge) { deba@417: Node target = _graph.target(edge); deba@417: _predMap.set(target, edge); deba@417: _edgeStack.push(edge); deba@417: } deba@417: deba@417: void examine(const Arc& edge) { deba@417: Node source = _graph.source(edge); deba@417: Node target = _graph.target(edge); deba@417: if (source == target && _graph.direction(edge)) { deba@417: _compMap.set(edge, _compNum); deba@417: ++_compNum; deba@417: return; deba@417: } deba@417: if (_numMap[target] < _numMap[source]) { deba@417: if (_predMap[source] != _graph.oppositeArc(edge)) { deba@417: _edgeStack.push(edge); deba@417: } deba@417: } deba@417: if (_predMap[source] != INVALID && deba@417: target == _graph.source(_predMap[source])) { deba@417: return; deba@417: } deba@417: if (_retMap[source] > _numMap[target]) { deba@417: _retMap.set(source, _numMap[target]); deba@417: } deba@417: } deba@417: deba@417: void backtrack(const Arc& edge) { deba@417: Node source = _graph.source(edge); deba@417: Node target = _graph.target(edge); deba@417: if (_retMap[source] > _retMap[target]) { deba@417: _retMap.set(source, _retMap[target]); deba@417: } deba@417: if (_numMap[source] <= _retMap[target]) { deba@417: while (_edgeStack.top() != edge) { deba@417: _compMap.set(_edgeStack.top(), _compNum); deba@417: _edgeStack.pop(); deba@417: } deba@417: _compMap.set(edge, _compNum); deba@417: _edgeStack.pop(); deba@417: ++_compNum; deba@417: } deba@417: } deba@417: deba@417: private: deba@417: const Digraph& _graph; deba@417: ArcMap& _compMap; deba@417: int& _compNum; deba@417: deba@417: typename Digraph::template NodeMap _numMap; deba@417: typename Digraph::template NodeMap _retMap; deba@417: typename Digraph::template NodeMap _predMap; deba@417: std::stack _edgeStack; deba@417: int _num; deba@417: }; deba@417: deba@417: deba@417: template deba@417: class BiNodeConnectedCutNodesVisitor : public DfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::Arc Arc; deba@417: typedef typename Digraph::Edge Edge; deba@417: deba@417: BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap, deba@417: int& cutNum) deba@417: : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), deba@417: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@417: deba@417: void start(const Node& node) { deba@417: _predMap.set(node, INVALID); deba@417: rootCut = false; deba@417: } deba@417: deba@417: void reach(const Node& node) { deba@417: _numMap.set(node, _num); deba@417: _retMap.set(node, _num); deba@417: ++_num; deba@417: } deba@417: deba@417: void discover(const Arc& edge) { deba@417: _predMap.set(_graph.target(edge), _graph.source(edge)); deba@417: } deba@417: deba@417: void examine(const Arc& edge) { deba@417: if (_graph.source(edge) == _graph.target(edge) && deba@417: _graph.direction(edge)) { deba@417: if (!_cutMap[_graph.source(edge)]) { deba@417: _cutMap.set(_graph.source(edge), true); deba@417: ++_cutNum; deba@417: } deba@417: return; deba@417: } deba@417: if (_predMap[_graph.source(edge)] == _graph.target(edge)) return; deba@417: if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) { deba@417: _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]); deba@417: } deba@417: } deba@417: deba@417: void backtrack(const Arc& edge) { deba@417: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@417: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@417: } deba@417: if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) { deba@417: if (_predMap[_graph.source(edge)] != INVALID) { deba@417: if (!_cutMap[_graph.source(edge)]) { deba@417: _cutMap.set(_graph.source(edge), true); deba@417: ++_cutNum; deba@417: } deba@417: } else if (rootCut) { deba@417: if (!_cutMap[_graph.source(edge)]) { deba@417: _cutMap.set(_graph.source(edge), true); deba@417: ++_cutNum; deba@417: } deba@417: } else { deba@417: rootCut = true; deba@417: } deba@417: } deba@417: } deba@417: deba@417: private: deba@417: const Digraph& _graph; deba@417: NodeMap& _cutMap; deba@417: int& _cutNum; deba@417: deba@417: typename Digraph::template NodeMap _numMap; deba@417: typename Digraph::template NodeMap _retMap; deba@417: typename Digraph::template NodeMap _predMap; deba@417: std::stack _edgeStack; deba@417: int _num; deba@417: bool rootCut; deba@417: }; deba@417: deba@417: } deba@417: deba@417: template deba@417: int countBiNodeConnectedComponents(const Graph& graph); deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether an undirected graph is bi-node-connected. deba@417: /// alpar@761: /// This function checks whether the given undirected graph is kpeter@646: /// bi-node-connected, i.e. any two edges are on same circle. deba@417: /// kpeter@646: /// \return \c true if the graph bi-node-connected. kpeter@646: /// \note By definition, the empty graph is bi-node-connected. kpeter@646: /// kpeter@646: /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() deba@417: template deba@417: bool biNodeConnected(const Graph& graph) { deba@417: return countBiNodeConnectedComponents(graph) <= 1; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// alpar@761: /// \brief Count the number of bi-node-connected components of an kpeter@646: /// undirected graph. deba@417: /// kpeter@646: /// This function counts the number of bi-node-connected components of kpeter@646: /// the given undirected graph. deba@417: /// kpeter@646: /// The bi-node-connected components are the classes of an equivalence kpeter@646: /// relation on the edges of a undirected graph. Two edges are in the kpeter@646: /// same class if they are on same circle. kpeter@646: /// kpeter@646: /// \return The number of bi-node-connected components. kpeter@646: /// kpeter@646: /// \see biNodeConnected(), biNodeConnectedComponents() deba@417: template deba@417: int countBiNodeConnectedComponents(const Graph& graph) { deba@417: checkConcept(); deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: deba@419: using namespace _connectivity_bits; deba@417: deba@417: typedef CountBiNodeConnectedComponentsVisitor Visitor; deba@417: deba@417: int compNum = 0; deba@417: Visitor visitor(graph, compNum); deba@417: deba@417: DfsVisit dfs(graph, visitor); deba@417: dfs.init(); deba@417: deba@417: for (NodeIt it(graph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: dfs.start(); deba@417: } deba@417: } deba@417: return compNum; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Find the bi-node-connected components of an undirected graph. deba@417: /// kpeter@646: /// This function finds the bi-node-connected components of the given kpeter@646: /// undirected graph. kpeter@646: /// kpeter@646: /// The bi-node-connected components are the classes of an equivalence kpeter@646: /// relation on the edges of a undirected graph. Two edges are in the kpeter@646: /// same class if they are on same circle. deba@417: /// kpeter@578: /// \image html node_biconnected_components.png kpeter@578: /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth kpeter@578: /// kpeter@646: /// \param graph The undirected graph. kpeter@646: /// \retval compMap A writable edge map. The values will be set from 0 kpeter@646: /// to the number of the bi-node-connected components minus one. Each alpar@761: /// value of the map will be set exactly once, and the values of a kpeter@646: /// certain component will be set continuously. kpeter@646: /// \return The number of bi-node-connected components. kpeter@646: /// kpeter@646: /// \see biNodeConnected(), countBiNodeConnectedComponents() deba@417: template deba@417: int biNodeConnectedComponents(const Graph& graph, deba@417: EdgeMap& compMap) { deba@417: checkConcept(); deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: typedef typename Graph::Edge Edge; deba@417: checkConcept, EdgeMap>(); deba@417: deba@419: using namespace _connectivity_bits; deba@417: deba@417: typedef BiNodeConnectedComponentsVisitor Visitor; deba@417: deba@417: int compNum = 0; deba@417: Visitor visitor(graph, compMap, compNum); deba@417: deba@417: DfsVisit dfs(graph, visitor); deba@417: dfs.init(); deba@417: deba@417: for (NodeIt it(graph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: dfs.start(); deba@417: } deba@417: } deba@417: return compNum; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Find the bi-node-connected cut nodes in an undirected graph. deba@417: /// kpeter@646: /// This function finds the bi-node-connected cut nodes in the given kpeter@646: /// undirected graph. deba@417: /// kpeter@646: /// The bi-node-connected components are the classes of an equivalence kpeter@646: /// relation on the edges of a undirected graph. Two edges are in the kpeter@646: /// same class if they are on same circle. kpeter@646: /// The bi-node-connected components are separted by the cut nodes of kpeter@646: /// the components. kpeter@646: /// kpeter@646: /// \param graph The undirected graph. alpar@761: /// \retval cutMap A writable node map. The values will be set to kpeter@646: /// \c true for the nodes that separate two or more components kpeter@646: /// (exactly once for each cut node), and will not be changed for kpeter@646: /// other nodes. deba@417: /// \return The number of the cut nodes. kpeter@646: /// kpeter@646: /// \see biNodeConnected(), biNodeConnectedComponents() deba@417: template deba@417: int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) { deba@417: checkConcept(); deba@417: typedef typename Graph::Node Node; deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: checkConcept, NodeMap>(); deba@417: deba@419: using namespace _connectivity_bits; deba@417: deba@417: typedef BiNodeConnectedCutNodesVisitor Visitor; deba@417: deba@417: int cutNum = 0; deba@417: Visitor visitor(graph, cutMap, cutNum); deba@417: deba@417: DfsVisit dfs(graph, visitor); deba@417: dfs.init(); deba@417: deba@417: for (NodeIt it(graph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: dfs.start(); deba@417: } deba@417: } deba@417: return cutNum; deba@417: } deba@417: deba@419: namespace _connectivity_bits { deba@417: deba@417: template deba@417: class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::Arc Arc; deba@417: typedef typename Digraph::Edge Edge; deba@417: deba@417: CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum) deba@417: : _graph(graph), _compNum(compNum), deba@417: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@417: deba@417: void start(const Node& node) { deba@417: _predMap.set(node, INVALID); deba@417: } deba@417: deba@417: void reach(const Node& node) { deba@417: _numMap.set(node, _num); deba@417: _retMap.set(node, _num); deba@417: ++_num; deba@417: } deba@417: deba@417: void leave(const Node& node) { deba@417: if (_numMap[node] <= _retMap[node]) { deba@417: ++_compNum; deba@417: } deba@417: } deba@417: deba@417: void discover(const Arc& edge) { deba@417: _predMap.set(_graph.target(edge), edge); deba@417: } deba@417: deba@417: void examine(const Arc& edge) { deba@417: if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) { deba@417: return; deba@417: } deba@417: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@417: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@417: } deba@417: } deba@417: deba@417: void backtrack(const Arc& edge) { deba@417: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@417: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@417: } deba@417: } deba@417: deba@417: private: deba@417: const Digraph& _graph; deba@417: int& _compNum; deba@417: deba@417: typename Digraph::template NodeMap _numMap; deba@417: typename Digraph::template NodeMap _retMap; deba@417: typename Digraph::template NodeMap _predMap; deba@417: int _num; deba@417: }; deba@417: deba@417: template deba@417: class BiEdgeConnectedComponentsVisitor : public DfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::Arc Arc; deba@417: typedef typename Digraph::Edge Edge; deba@417: deba@417: BiEdgeConnectedComponentsVisitor(const Digraph& graph, deba@417: NodeMap& compMap, int &compNum) deba@417: : _graph(graph), _compMap(compMap), _compNum(compNum), deba@417: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@417: deba@417: void start(const Node& node) { deba@417: _predMap.set(node, INVALID); deba@417: } deba@417: deba@417: void reach(const Node& node) { deba@417: _numMap.set(node, _num); deba@417: _retMap.set(node, _num); deba@417: _nodeStack.push(node); deba@417: ++_num; deba@417: } deba@417: deba@417: void leave(const Node& node) { deba@417: if (_numMap[node] <= _retMap[node]) { deba@417: while (_nodeStack.top() != node) { deba@417: _compMap.set(_nodeStack.top(), _compNum); deba@417: _nodeStack.pop(); deba@417: } deba@417: _compMap.set(node, _compNum); deba@417: _nodeStack.pop(); deba@417: ++_compNum; deba@417: } deba@417: } deba@417: deba@417: void discover(const Arc& edge) { deba@417: _predMap.set(_graph.target(edge), edge); deba@417: } deba@417: deba@417: void examine(const Arc& edge) { deba@417: if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) { deba@417: return; deba@417: } deba@417: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@417: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@417: } deba@417: } deba@417: deba@417: void backtrack(const Arc& edge) { deba@417: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@417: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@417: } deba@417: } deba@417: deba@417: private: deba@417: const Digraph& _graph; deba@417: NodeMap& _compMap; deba@417: int& _compNum; deba@417: deba@417: typename Digraph::template NodeMap _numMap; deba@417: typename Digraph::template NodeMap _retMap; deba@417: typename Digraph::template NodeMap _predMap; deba@417: std::stack _nodeStack; deba@417: int _num; deba@417: }; deba@417: deba@417: deba@417: template deba@417: class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::Arc Arc; deba@417: typedef typename Digraph::Edge Edge; deba@417: deba@417: BiEdgeConnectedCutEdgesVisitor(const Digraph& graph, deba@417: ArcMap& cutMap, int &cutNum) deba@417: : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), deba@417: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@417: deba@417: void start(const Node& node) { deba@417: _predMap[node] = INVALID; deba@417: } deba@417: deba@417: void reach(const Node& node) { deba@417: _numMap.set(node, _num); deba@417: _retMap.set(node, _num); deba@417: ++_num; deba@417: } deba@417: deba@417: void leave(const Node& node) { deba@417: if (_numMap[node] <= _retMap[node]) { deba@417: if (_predMap[node] != INVALID) { deba@417: _cutMap.set(_predMap[node], true); deba@417: ++_cutNum; deba@417: } deba@417: } deba@417: } deba@417: deba@417: void discover(const Arc& edge) { deba@417: _predMap.set(_graph.target(edge), edge); deba@417: } deba@417: deba@417: void examine(const Arc& edge) { deba@417: if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) { deba@417: return; deba@417: } deba@417: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@417: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@417: } deba@417: } deba@417: deba@417: void backtrack(const Arc& edge) { deba@417: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@417: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@417: } deba@417: } deba@417: deba@417: private: deba@417: const Digraph& _graph; deba@417: ArcMap& _cutMap; deba@417: int& _cutNum; deba@417: deba@417: typename Digraph::template NodeMap _numMap; deba@417: typename Digraph::template NodeMap _retMap; deba@417: typename Digraph::template NodeMap _predMap; deba@417: int _num; deba@417: }; deba@417: } deba@417: deba@417: template deba@417: int countBiEdgeConnectedComponents(const Graph& graph); deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether an undirected graph is bi-edge-connected. deba@417: /// alpar@761: /// This function checks whether the given undirected graph is kpeter@646: /// bi-edge-connected, i.e. any two nodes are connected with at least kpeter@646: /// two edge-disjoint paths. deba@417: /// kpeter@646: /// \return \c true if the graph is bi-edge-connected. kpeter@646: /// \note By definition, the empty graph is bi-edge-connected. kpeter@646: /// kpeter@646: /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents() deba@417: template deba@417: bool biEdgeConnected(const Graph& graph) { deba@417: return countBiEdgeConnectedComponents(graph) <= 1; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Count the number of bi-edge-connected components of an kpeter@646: /// undirected graph. deba@417: /// kpeter@646: /// This function counts the number of bi-edge-connected components of kpeter@646: /// the given undirected graph. deba@417: /// kpeter@646: /// The bi-edge-connected components are the classes of an equivalence kpeter@646: /// relation on the nodes of an undirected graph. Two nodes are in the kpeter@646: /// same class if they are connected with at least two edge-disjoint kpeter@646: /// paths. kpeter@646: /// kpeter@646: /// \return The number of bi-edge-connected components. kpeter@646: /// kpeter@646: /// \see biEdgeConnected(), biEdgeConnectedComponents() deba@417: template deba@417: int countBiEdgeConnectedComponents(const Graph& graph) { deba@417: checkConcept(); deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: deba@419: using namespace _connectivity_bits; deba@417: deba@417: typedef CountBiEdgeConnectedComponentsVisitor Visitor; deba@417: deba@417: int compNum = 0; deba@417: Visitor visitor(graph, compNum); deba@417: deba@417: DfsVisit dfs(graph, visitor); deba@417: dfs.init(); deba@417: deba@417: for (NodeIt it(graph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: dfs.start(); deba@417: } deba@417: } deba@417: return compNum; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Find the bi-edge-connected components of an undirected graph. deba@417: /// kpeter@646: /// This function finds the bi-edge-connected components of the given kpeter@646: /// undirected graph. kpeter@646: /// kpeter@646: /// The bi-edge-connected components are the classes of an equivalence kpeter@646: /// relation on the nodes of an undirected graph. Two nodes are in the kpeter@646: /// same class if they are connected with at least two edge-disjoint kpeter@646: /// paths. deba@417: /// kpeter@578: /// \image html edge_biconnected_components.png kpeter@578: /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth kpeter@578: /// kpeter@646: /// \param graph The undirected graph. deba@417: /// \retval compMap A writable node map. The values will be set from 0 to kpeter@646: /// the number of the bi-edge-connected components minus one. Each value kpeter@646: /// of the map will be set exactly once, and the values of a certain kpeter@646: /// component will be set continuously. kpeter@646: /// \return The number of bi-edge-connected components. kpeter@646: /// kpeter@646: /// \see biEdgeConnected(), countBiEdgeConnectedComponents() deba@417: template deba@417: int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { deba@417: checkConcept(); deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: typedef typename Graph::Node Node; deba@417: checkConcept, NodeMap>(); deba@417: deba@419: using namespace _connectivity_bits; deba@417: deba@417: typedef BiEdgeConnectedComponentsVisitor Visitor; deba@417: deba@417: int compNum = 0; deba@417: Visitor visitor(graph, compMap, compNum); deba@417: deba@417: DfsVisit dfs(graph, visitor); deba@417: dfs.init(); deba@417: deba@417: for (NodeIt it(graph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: dfs.start(); deba@417: } deba@417: } deba@417: return compNum; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Find the bi-edge-connected cut edges in an undirected graph. deba@417: /// kpeter@646: /// This function finds the bi-edge-connected cut edges in the given alpar@761: /// undirected graph. deba@417: /// kpeter@646: /// The bi-edge-connected components are the classes of an equivalence kpeter@646: /// relation on the nodes of an undirected graph. Two nodes are in the kpeter@646: /// same class if they are connected with at least two edge-disjoint kpeter@646: /// paths. kpeter@646: /// The bi-edge-connected components are separted by the cut edges of kpeter@646: /// the components. kpeter@646: /// kpeter@646: /// \param graph The undirected graph. kpeter@646: /// \retval cutMap A writable edge map. The values will be set to \c true kpeter@646: /// for the cut edges (exactly once for each cut edge), and will not be kpeter@646: /// changed for other edges. deba@417: /// \return The number of cut edges. kpeter@646: /// kpeter@646: /// \see biEdgeConnected(), biEdgeConnectedComponents() deba@417: template deba@417: int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { deba@417: checkConcept(); deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: typedef typename Graph::Edge Edge; deba@417: checkConcept, EdgeMap>(); deba@417: deba@419: using namespace _connectivity_bits; deba@417: deba@417: typedef BiEdgeConnectedCutEdgesVisitor Visitor; deba@417: deba@417: int cutNum = 0; deba@417: Visitor visitor(graph, cutMap, cutNum); deba@417: deba@417: DfsVisit dfs(graph, visitor); deba@417: dfs.init(); deba@417: deba@417: for (NodeIt it(graph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: dfs.start(); deba@417: } deba@417: } deba@417: return cutNum; deba@417: } deba@417: deba@417: deba@419: namespace _connectivity_bits { deba@417: deba@417: template deba@417: class TopologicalSortVisitor : public DfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::Arc edge; deba@417: deba@417: TopologicalSortVisitor(IntNodeMap& order, int num) deba@417: : _order(order), _num(num) {} deba@417: deba@417: void leave(const Node& node) { deba@417: _order.set(node, --_num); deba@417: } deba@417: deba@417: private: deba@417: IntNodeMap& _order; deba@417: int _num; deba@417: }; deba@417: deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether a digraph is DAG. kpeter@646: /// kpeter@646: /// This function checks whether the given digraph is DAG, i.e. kpeter@646: /// \e Directed \e Acyclic \e Graph. kpeter@646: /// \return \c true if there is no directed cycle in the digraph. kpeter@646: /// \see acyclic() kpeter@646: template kpeter@646: bool dag(const Digraph& digraph) { kpeter@646: kpeter@646: checkConcept(); kpeter@646: kpeter@646: typedef typename Digraph::Node Node; kpeter@646: typedef typename Digraph::NodeIt NodeIt; kpeter@646: typedef typename Digraph::Arc Arc; kpeter@646: kpeter@646: typedef typename Digraph::template NodeMap ProcessedMap; kpeter@646: kpeter@646: typename Dfs::template SetProcessedMap:: kpeter@646: Create dfs(digraph); kpeter@646: kpeter@646: ProcessedMap processed(digraph); kpeter@646: dfs.processedMap(processed); kpeter@646: kpeter@646: dfs.init(); kpeter@646: for (NodeIt it(digraph); it != INVALID; ++it) { kpeter@646: if (!dfs.reached(it)) { kpeter@646: dfs.addSource(it); kpeter@646: while (!dfs.emptyQueue()) { kpeter@646: Arc arc = dfs.nextArc(); kpeter@646: Node target = digraph.target(arc); kpeter@646: if (dfs.reached(target) && !processed[target]) { kpeter@646: return false; kpeter@646: } kpeter@646: dfs.processNextArc(); kpeter@646: } kpeter@646: } kpeter@646: } kpeter@646: return true; kpeter@646: } kpeter@646: kpeter@646: /// \ingroup graph_properties kpeter@646: /// deba@417: /// \brief Sort the nodes of a DAG into topolgical order. deba@417: /// kpeter@646: /// This function sorts the nodes of the given acyclic digraph (DAG) kpeter@646: /// into topolgical order. deba@417: /// kpeter@646: /// \param digraph The digraph, which must be DAG. deba@417: /// \retval order A writable node map. The values will be set from 0 to kpeter@646: /// the number of the nodes in the digraph minus one. Each value of the kpeter@646: /// map will be set exactly once, and the values will be set descending kpeter@646: /// order. deba@417: /// kpeter@646: /// \see dag(), checkedTopologicalSort() deba@417: template kpeter@646: void topologicalSort(const Digraph& digraph, NodeMap& order) { deba@419: using namespace _connectivity_bits; deba@417: deba@417: checkConcept(); deba@417: checkConcept, NodeMap>(); deba@417: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::NodeIt NodeIt; deba@417: typedef typename Digraph::Arc Arc; deba@417: deba@417: TopologicalSortVisitor kpeter@646: visitor(order, countNodes(digraph)); deba@417: deba@417: DfsVisit > kpeter@646: dfs(digraph, visitor); deba@417: deba@417: dfs.init(); kpeter@646: for (NodeIt it(digraph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: dfs.start(); deba@417: } deba@417: } deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// deba@417: /// \brief Sort the nodes of a DAG into topolgical order. deba@417: /// kpeter@646: /// This function sorts the nodes of the given acyclic digraph (DAG) kpeter@646: /// into topolgical order and also checks whether the given digraph kpeter@646: /// is DAG. deba@417: /// kpeter@646: /// \param digraph The digraph. kpeter@646: /// \retval order A readable and writable node map. The values will be alpar@761: /// set from 0 to the number of the nodes in the digraph minus one. kpeter@646: /// Each value of the map will be set exactly once, and the values will kpeter@646: /// be set descending order. kpeter@646: /// \return \c false if the digraph is not DAG. deba@417: /// kpeter@646: /// \see dag(), topologicalSort() deba@417: template deba@419: bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { deba@419: using namespace _connectivity_bits; deba@417: deba@417: checkConcept(); deba@417: checkConcept, deba@417: NodeMap>(); deba@417: deba@417: typedef typename Digraph::Node Node; deba@417: typedef typename Digraph::NodeIt NodeIt; deba@417: typedef typename Digraph::Arc Arc; deba@417: deba@419: for (NodeIt it(digraph); it != INVALID; ++it) { deba@419: order.set(it, -1); deba@419: } deba@417: deba@417: TopologicalSortVisitor deba@419: visitor(order, countNodes(digraph)); deba@417: deba@417: DfsVisit > deba@419: dfs(digraph, visitor); deba@417: deba@417: dfs.init(); deba@419: for (NodeIt it(digraph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: while (!dfs.emptyQueue()) { deba@419: Arc arc = dfs.nextArc(); deba@419: Node target = digraph.target(arc); deba@417: if (dfs.reached(target) && order[target] == -1) { deba@417: return false; deba@417: } deba@417: dfs.processNextArc(); deba@417: } deba@417: } deba@417: } deba@417: return true; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether an undirected graph is acyclic. deba@417: /// kpeter@646: /// This function checks whether the given undirected graph is acyclic. kpeter@646: /// \return \c true if there is no cycle in the graph. kpeter@646: /// \see dag() deba@417: template deba@417: bool acyclic(const Graph& graph) { deba@417: checkConcept(); deba@417: typedef typename Graph::Node Node; deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: typedef typename Graph::Arc Arc; deba@417: Dfs dfs(graph); deba@417: dfs.init(); deba@417: for (NodeIt it(graph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: dfs.addSource(it); deba@417: while (!dfs.emptyQueue()) { kpeter@646: Arc arc = dfs.nextArc(); kpeter@646: Node source = graph.source(arc); kpeter@646: Node target = graph.target(arc); deba@417: if (dfs.reached(target) && kpeter@646: dfs.predArc(source) != graph.oppositeArc(arc)) { deba@417: return false; deba@417: } deba@417: dfs.processNextArc(); deba@417: } deba@417: } deba@417: } deba@417: return true; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether an undirected graph is tree. deba@417: /// kpeter@646: /// This function checks whether the given undirected graph is tree. kpeter@646: /// \return \c true if the graph is acyclic and connected. kpeter@646: /// \see acyclic(), connected() deba@417: template deba@417: bool tree(const Graph& graph) { deba@417: checkConcept(); deba@417: typedef typename Graph::Node Node; deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: typedef typename Graph::Arc Arc; kpeter@645: if (NodeIt(graph) == INVALID) return true; deba@417: Dfs dfs(graph); deba@417: dfs.init(); deba@417: dfs.addSource(NodeIt(graph)); deba@417: while (!dfs.emptyQueue()) { kpeter@646: Arc arc = dfs.nextArc(); kpeter@646: Node source = graph.source(arc); kpeter@646: Node target = graph.target(arc); deba@417: if (dfs.reached(target) && kpeter@646: dfs.predArc(source) != graph.oppositeArc(arc)) { deba@417: return false; deba@417: } deba@417: dfs.processNextArc(); deba@417: } deba@417: for (NodeIt it(graph); it != INVALID; ++it) { deba@417: if (!dfs.reached(it)) { deba@417: return false; deba@417: } deba@417: } deba@417: return true; deba@417: } deba@417: deba@419: namespace _connectivity_bits { deba@417: deba@417: template deba@417: class BipartiteVisitor : public BfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Arc Arc; deba@417: typedef typename Digraph::Node Node; deba@417: deba@417: BipartiteVisitor(const Digraph& graph, bool& bipartite) deba@417: : _graph(graph), _part(graph), _bipartite(bipartite) {} deba@417: deba@417: void start(const Node& node) { deba@417: _part[node] = true; deba@417: } deba@417: void discover(const Arc& edge) { deba@417: _part.set(_graph.target(edge), !_part[_graph.source(edge)]); deba@417: } deba@417: void examine(const Arc& edge) { deba@417: _bipartite = _bipartite && deba@417: _part[_graph.target(edge)] != _part[_graph.source(edge)]; deba@417: } deba@417: deba@417: private: deba@417: deba@417: const Digraph& _graph; deba@417: typename Digraph::template NodeMap _part; deba@417: bool& _bipartite; deba@417: }; deba@417: deba@417: template deba@417: class BipartitePartitionsVisitor : public BfsVisitor { deba@417: public: deba@417: typedef typename Digraph::Arc Arc; deba@417: typedef typename Digraph::Node Node; deba@417: deba@417: BipartitePartitionsVisitor(const Digraph& graph, deba@417: PartMap& part, bool& bipartite) deba@417: : _graph(graph), _part(part), _bipartite(bipartite) {} deba@417: deba@417: void start(const Node& node) { deba@417: _part.set(node, true); deba@417: } deba@417: void discover(const Arc& edge) { deba@417: _part.set(_graph.target(edge), !_part[_graph.source(edge)]); deba@417: } deba@417: void examine(const Arc& edge) { deba@417: _bipartite = _bipartite && deba@417: _part[_graph.target(edge)] != _part[_graph.source(edge)]; deba@417: } deba@417: deba@417: private: deba@417: deba@417: const Digraph& _graph; deba@417: PartMap& _part; deba@417: bool& _bipartite; deba@417: }; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether an undirected graph is bipartite. deba@417: /// kpeter@646: /// The function checks whether the given undirected graph is bipartite. kpeter@646: /// \return \c true if the graph is bipartite. kpeter@646: /// kpeter@646: /// \see bipartitePartitions() deba@417: template kpeter@646: bool bipartite(const Graph &graph){ deba@419: using namespace _connectivity_bits; deba@417: deba@417: checkConcept(); deba@417: deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: typedef typename Graph::ArcIt ArcIt; deba@417: deba@417: bool bipartite = true; deba@417: deba@417: BipartiteVisitor deba@417: visitor(graph, bipartite); deba@417: BfsVisit > deba@417: bfs(graph, visitor); deba@417: bfs.init(); deba@417: for(NodeIt it(graph); it != INVALID; ++it) { deba@417: if(!bfs.reached(it)){ deba@417: bfs.addSource(it); deba@417: while (!bfs.emptyQueue()) { deba@417: bfs.processNextNode(); deba@417: if (!bipartite) return false; deba@417: } deba@417: } deba@417: } deba@417: return true; deba@417: } deba@417: kpeter@578: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Find the bipartite partitions of an undirected graph. deba@417: /// kpeter@646: /// This function checks whether the given undirected graph is bipartite kpeter@646: /// and gives back the bipartite partitions. kpeter@578: /// kpeter@578: /// \image html bipartite_partitions.png kpeter@578: /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth kpeter@578: /// deba@417: /// \param graph The undirected graph. kpeter@646: /// \retval partMap A writable node map of \c bool (or convertible) value kpeter@646: /// type. The values will be set to \c true for one component and kpeter@646: /// \c false for the other one. kpeter@646: /// \return \c true if the graph is bipartite, \c false otherwise. kpeter@646: /// kpeter@646: /// \see bipartite() deba@417: template kpeter@646: bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ deba@419: using namespace _connectivity_bits; deba@417: deba@417: checkConcept(); kpeter@646: checkConcept, NodeMap>(); deba@417: deba@417: typedef typename Graph::Node Node; deba@417: typedef typename Graph::NodeIt NodeIt; deba@417: typedef typename Graph::ArcIt ArcIt; deba@417: deba@417: bool bipartite = true; deba@417: deba@417: BipartitePartitionsVisitor deba@417: visitor(graph, partMap, bipartite); deba@417: BfsVisit > deba@417: bfs(graph, visitor); deba@417: bfs.init(); deba@417: for(NodeIt it(graph); it != INVALID; ++it) { deba@417: if(!bfs.reached(it)){ deba@417: bfs.addSource(it); deba@417: while (!bfs.emptyQueue()) { deba@417: bfs.processNextNode(); deba@417: if (!bipartite) return false; deba@417: } deba@417: } deba@417: } deba@417: return true; deba@417: } deba@417: kpeter@646: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether the given graph contains no loop arcs/edges. kpeter@646: /// kpeter@646: /// This function returns \c true if there are no loop arcs/edges in kpeter@646: /// the given graph. It works for both directed and undirected graphs. kpeter@646: template kpeter@646: bool loopFree(const Graph& graph) { kpeter@646: for (typename Graph::ArcIt it(graph); it != INVALID; ++it) { kpeter@646: if (graph.source(it) == graph.target(it)) return false; deba@417: } deba@417: return true; deba@417: } deba@417: kpeter@646: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether the given graph contains no parallel arcs/edges. kpeter@646: /// kpeter@646: /// This function returns \c true if there are no parallel arcs/edges in kpeter@646: /// the given graph. It works for both directed and undirected graphs. kpeter@645: template kpeter@645: bool parallelFree(const Graph& graph) { kpeter@645: typename Graph::template NodeMap reached(graph, 0); kpeter@645: int cnt = 1; kpeter@645: for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { kpeter@645: for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { kpeter@645: if (reached[graph.target(a)] == cnt) return false; kpeter@645: reached[graph.target(a)] = cnt; deba@417: } kpeter@645: ++cnt; deba@417: } deba@417: return true; deba@417: } deba@417: kpeter@646: /// \ingroup graph_properties deba@417: /// kpeter@646: /// \brief Check whether the given graph is simple. kpeter@646: /// kpeter@646: /// This function returns \c true if the given graph is simple, i.e. kpeter@646: /// it contains no loop arcs/edges and no parallel arcs/edges. kpeter@646: /// The function works for both directed and undirected graphs. kpeter@646: /// \see loopFree(), parallelFree() kpeter@645: template kpeter@645: bool simpleGraph(const Graph& graph) { kpeter@645: typename Graph::template NodeMap reached(graph, 0); kpeter@645: int cnt = 1; kpeter@645: for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { kpeter@645: reached[n] = cnt; kpeter@645: for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { kpeter@645: if (reached[graph.target(a)] == cnt) return false; kpeter@645: reached[graph.target(a)] = cnt; deba@417: } kpeter@645: ++cnt; deba@417: } deba@417: return true; deba@417: } deba@417: deba@417: } //namespace lemon deba@417: deba@419: #endif //LEMON_CONNECTIVITY_H