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 deba@1740: #include deba@1698: #include deba@1750: #include deba@1750: #include deba@1698: deba@1698: #include deba@1698: #include deba@1698: #include deba@1698: deba@1750: #include deba@1750: #include deba@1750: deba@1750: #include deba@1750: #include 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 deba@1750: bool connected(const UndirGraph& graph) { deba@1750: checkConcept(); deba@1750: typedef typename UndirGraph::NodeIt NodeIt; deba@1750: if (NodeIt(graph) == INVALID) return false; deba@1750: Dfs 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 deba@1750: int countConnectedComponents(const UndirGraph &graph) { deba@1750: checkConcept(); deba@1750: typedef typename UndirGraph::Node Node; deba@1750: typedef typename UndirGraph::Edge Edge; deba@1750: deba@1750: typedef NullMap PredMap; deba@1750: typedef NullMap DistMap; deba@1750: deba@1750: int compNum = 0; deba@1750: typename Bfs:: deba@1750: template DefPredMap:: deba@1750: template DefDistMap:: 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 deba@1750: int connectedComponents(const UndirGraph &graph, NodeMap &compMap) { deba@1750: checkConcept(); deba@1750: typedef typename UndirGraph::Node Node; deba@1750: typedef typename UndirGraph::Edge Edge; deba@1750: checkConcept, NodeMap>(); deba@1750: deba@1750: typedef NullMap PredMap; deba@1750: typedef NullMap DistMap; deba@1750: deba@1750: int compNum = 0; deba@1750: typename Bfs:: deba@1750: template DefPredMap:: deba@1750: template DefDistMap:: 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 deba@1750: struct LeaveOrderVisitor : public DfsVisitor { 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 deba@1750: struct FillMapVisitor : public DfsVisitor { 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 deba@1750: struct StronglyConnectedCutEdgesVisitor : public DfsVisitor { 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 _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 deba@1750: bool stronglyConnected(const Graph& graph) { deba@1750: checkConcept(); 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 Visitor; deba@1750: Visitor visitor; deba@1750: deba@1750: DfsVisit 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 RGraph; deba@1750: RGraph rgraph(graph); deba@1750: deba@1750: typedef DfsVisitor RVisitor; deba@1750: RVisitor rvisitor; deba@1750: deba@1750: DfsVisit 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 deba@1750: int countStronglyConnectedComponents(const Graph& graph) { deba@1750: checkConcept(); 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 Container; deba@1750: typedef typename Container::iterator Iterator; deba@1750: deba@1750: Container nodes(countNodes(graph)); deba@1750: typedef LeaveOrderVisitor Visitor; deba@1750: Visitor visitor(nodes.begin()); deba@1750: deba@1750: DfsVisit 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 RGraph; deba@1750: deba@1750: RGraph rgraph(graph); deba@1750: deba@1750: typedef DfsVisitor RVisitor; deba@1750: RVisitor rvisitor; deba@1750: deba@1750: DfsVisit 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 deba@1750: int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) { deba@1750: checkConcept(); deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::NodeIt NodeIt; deba@1750: checkConcept, NodeMap>(); deba@1750: deba@1750: using namespace _topology_bits; deba@1750: deba@1750: typedef std::vector Container; deba@1750: typedef typename Container::iterator Iterator; deba@1750: deba@1750: Container nodes(countNodes(graph)); deba@1750: typedef LeaveOrderVisitor Visitor; deba@1750: Visitor visitor(nodes.begin()); deba@1750: deba@1750: DfsVisit 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 RGraph; deba@1750: deba@1750: RGraph rgraph(graph); deba@1750: deba@1750: int compNum = 0; deba@1750: deba@1750: typedef FillMapVisitor RVisitor; deba@1750: RVisitor rvisitor(compMap, compNum); deba@1750: deba@1750: DfsVisit 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 deba@1750: int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { deba@1750: checkConcept(); deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::Edge Edge; deba@1750: typedef typename Graph::NodeIt NodeIt; deba@1750: checkConcept, EdgeMap>(); deba@1750: deba@1750: using namespace _topology_bits; deba@1750: deba@1750: typedef std::vector Container; deba@1750: typedef typename Container::iterator Iterator; deba@1750: deba@1750: Container nodes(countNodes(graph)); deba@1750: typedef LeaveOrderVisitor Visitor; deba@1750: Visitor visitor(nodes.begin()); deba@1750: deba@1750: DfsVisit 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 RGraph; deba@1750: deba@1750: RGraph rgraph(graph); deba@1750: deba@1750: int cutNum = 0; deba@1750: deba@1750: typedef StronglyConnectedCutEdgesVisitor RVisitor; deba@1750: RVisitor rvisitor(rgraph, cutMap, cutNum); deba@1750: deba@1750: DfsVisit 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 deba@1750: class CountNodeBiconnectedComponentsVisitor : public DfsVisitor { 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 _numMap; deba@1750: typename Graph::template NodeMap _retMap; deba@1750: typename Graph::template NodeMap _predMap; deba@1750: int _num; deba@1750: }; deba@1750: deba@1750: template deba@1750: class NodeBiconnectedComponentsVisitor : public DfsVisitor { 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 _numMap; deba@1750: typename Graph::template NodeMap _retMap; deba@1750: typename Graph::template NodeMap _predMap; deba@1750: std::stack _edgeStack; deba@1750: int _num; deba@1750: }; deba@1750: deba@1750: deba@1750: template deba@1750: class NodeBiconnectedCutNodesVisitor : public DfsVisitor { 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 _numMap; deba@1750: typename Graph::template NodeMap _retMap; deba@1750: typename Graph::template NodeMap _predMap; deba@1750: std::stack _edgeStack; deba@1750: int _num; deba@1750: bool rootCut; deba@1750: }; deba@1750: deba@1750: } deba@1750: deba@1750: template 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 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 deba@1750: int countNodeBiconnectedComponents(const UndirGraph& graph) { deba@1750: checkConcept(); deba@1750: typedef typename UndirGraph::NodeIt NodeIt; deba@1750: deba@1750: using namespace _topology_bits; deba@1750: deba@1750: typedef CountNodeBiconnectedComponentsVisitor Visitor; deba@1750: deba@1750: int compNum = 0; deba@1750: Visitor visitor(graph, compNum); deba@1750: deba@1750: DfsVisit 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 deba@1767: int biNodeConnectedComponents(const UndirGraph& graph, deba@1750: UndirEdgeMap& compMap) { deba@1750: checkConcept(); deba@1750: typedef typename UndirGraph::NodeIt NodeIt; deba@1750: typedef typename UndirGraph::UndirEdge UndirEdge; deba@1750: checkConcept, UndirEdgeMap>(); deba@1750: deba@1750: using namespace _topology_bits; deba@1750: deba@1750: typedef NodeBiconnectedComponentsVisitor Visitor; deba@1750: deba@1750: int compNum = 0; deba@1750: Visitor visitor(graph, compMap, compNum); deba@1750: deba@1750: DfsVisit 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 deba@1767: int biNodeConnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) { deba@1750: checkConcept(); deba@1750: typedef typename UndirGraph::Node Node; deba@1750: typedef typename UndirGraph::NodeIt NodeIt; deba@1750: checkConcept, NodeMap>(); deba@1750: deba@1750: using namespace _topology_bits; deba@1750: deba@1750: typedef NodeBiconnectedCutNodesVisitor Visitor; deba@1750: deba@1750: int cutNum = 0; deba@1750: Visitor visitor(graph, cutMap, cutNum); deba@1750: deba@1750: DfsVisit 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 deba@1750: class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor { 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 _numMap; deba@1750: typename Graph::template NodeMap _retMap; deba@1750: typename Graph::template NodeMap _predMap; deba@1750: int _num; deba@1750: }; deba@1750: deba@1750: template deba@1750: class EdgeBiconnectedComponentsVisitor : public DfsVisitor { 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 _numMap; deba@1750: typename Graph::template NodeMap _retMap; deba@1750: typename Graph::template NodeMap _predMap; deba@1750: std::stack _nodeStack; deba@1750: int _num; deba@1750: }; deba@1750: deba@1750: deba@1750: template deba@1750: class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor { 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 _numMap; deba@1750: typename Graph::template NodeMap _retMap; deba@1750: typename Graph::template NodeMap _predMap; deba@1750: int _num; deba@1750: }; deba@1750: } deba@1750: deba@1750: template 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 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 deba@1750: int countEdgeBiconnectedComponents(const UndirGraph& graph) { deba@1750: checkConcept(); deba@1750: typedef typename UndirGraph::NodeIt NodeIt; deba@1750: deba@1750: using namespace _topology_bits; deba@1750: deba@1750: typedef CountEdgeBiconnectedComponentsVisitor Visitor; deba@1750: deba@1750: int compNum = 0; deba@1750: Visitor visitor(graph, compNum); deba@1750: deba@1750: DfsVisit 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 deba@1767: int biEdgeConnectedComponents(const UndirGraph& graph, NodeMap& compMap) { deba@1750: checkConcept(); deba@1750: typedef typename UndirGraph::NodeIt NodeIt; deba@1750: typedef typename UndirGraph::Node Node; deba@1750: checkConcept, NodeMap>(); deba@1750: deba@1750: using namespace _topology_bits; deba@1750: deba@1750: typedef EdgeBiconnectedComponentsVisitor Visitor; deba@1750: deba@1750: int compNum = 0; deba@1750: Visitor visitor(graph, compMap, compNum); deba@1750: deba@1750: DfsVisit 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 deba@1767: int biEdgeConnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { deba@1750: checkConcept(); deba@1750: typedef typename UndirGraph::NodeIt NodeIt; deba@1750: typedef typename UndirGraph::UndirEdge UndirEdge; deba@1750: checkConcept, UndirEdgeMap>(); deba@1750: deba@1750: using namespace _topology_bits; deba@1750: deba@1750: typedef EdgeBiconnectedCutEdgesVisitor Visitor; deba@1750: deba@1750: int cutNum = 0; deba@1750: Visitor visitor(graph, cutMap, cutNum); deba@1750: deba@1750: DfsVisit 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 deba@1750: class TopologicalSortVisitor : public DfsVisitor { 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 deba@1750: void topologicalSort(const Graph& graph, NodeMap& order) { deba@1750: using namespace _topology_bits; deba@1750: deba@1750: checkConcept(); deba@1750: checkConcept, 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 deba@1750: visitor(order, countNodes(graph)); deba@1750: deba@1750: DfsVisit > 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 deba@1750: bool checkedTopologicalSort(const Graph& graph, NodeMap& order) { deba@1698: using namespace _topology_bits; deba@1698: deba@1698: checkConcept(); deba@1698: checkConcept, 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(); deba@1698: deba@1750: TopologicalSortVisitor deba@1750: visitor(order, countNodes(graph)); deba@1698: deba@1750: DfsVisit > 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 deba@1698: bool dag(const Graph& graph) { deba@1698: deba@1698: checkConcept(); 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 ProcessedMap; deba@1698: deba@1698: typename Dfs::template DefProcessedMap:: 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 deba@1698: bool acyclic(const UndirGraph& graph) { deba@1698: checkConcept(); deba@1698: typedef typename UndirGraph::Node Node; deba@1698: typedef typename UndirGraph::NodeIt NodeIt; deba@1698: typedef typename UndirGraph::Edge Edge; deba@1698: Dfs 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 deba@1698: bool tree(const UndirGraph& graph) { deba@1698: checkConcept(); deba@1698: typedef typename UndirGraph::Node Node; deba@1698: typedef typename UndirGraph::NodeIt NodeIt; deba@1698: typedef typename UndirGraph::Edge Edge; deba@1698: Dfs 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 deba@1750: bool bipartite(const UndirGraph& graph) { deba@1740: checkConcept(); 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 dfs(graph); deba@1740: dfs.init(); deba@1750: typename UndirGraph::template NodeMap 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