deba@1698: /* -*- C++ -*- deba@1698: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1698: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1698: * deba@1698: * Permission to use, modify and distribute this software is granted deba@1698: * provided that this copyright notice appears in all copies. For deba@1698: * precise terms see the accompanying LICENSE file. deba@1698: * deba@1698: * This software is provided "AS IS" with no warranty of any kind, deba@1698: * express or implied, and with no claim as to its suitability for any deba@1698: * purpose. deba@1698: * deba@1698: */ deba@1698: deba@1698: #ifndef LEMON_TOPOLOGY_H deba@1698: #define LEMON_TOPOLOGY_H deba@1698: deba@1698: #include deba@1740: #include deba@1698: #include deba@1750: #include deba@1750: #include deba@1698: alpar@2260: #include alpar@2260: #include deba@1698: #include deba@1698: deba@1750: #include deba@2038: #include deba@1750: deba@1750: #include deba@1750: #include deba@1750: deba@2429: /// \ingroup graph_prop 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1750: /// \brief Check that the given undirected graph is connected. deba@1750: /// deba@1750: /// Check that the given undirected graph connected. deba@1750: /// \param graph The undirected graph. deba@1750: /// \return %True when there is path between any two nodes in the graph. alpar@1807: /// \note By definition, the empty graph is connected. klao@1909: template klao@1909: bool connected(const UGraph& graph) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::NodeIt NodeIt; alpar@1807: if (NodeIt(graph) == INVALID) return true; klao@1909: 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1750: /// \brief Count the number of connected components of an undirected graph deba@1750: /// deba@1750: /// Count the number of connected components of an undirected graph deba@1750: /// deba@1793: /// \param graph The graph. It should be undirected. deba@1750: /// \return The number of components alpar@1807: /// \note By definition, the empty graph consists alpar@1807: /// of zero connected components. klao@1909: template klao@1909: int countConnectedComponents(const UGraph &graph) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::Node Node; klao@1909: typedef typename UGraph::Edge Edge; deba@1750: deba@1750: typedef NullMap PredMap; deba@1750: typedef NullMap DistMap; deba@1750: deba@1750: int compNum = 0; klao@1909: 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(); klao@1909: for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) { deba@1750: if (!bfs.reached(n)) { deba@1750: bfs.addSource(n); deba@1750: bfs.start(); deba@1750: ++compNum; deba@1750: } deba@1750: } deba@1750: return compNum; deba@1750: } deba@1750: deba@2429: /// \ingroup graph_prop deba@1750: /// deba@1750: /// \brief Find the connected components of an undirected graph deba@1750: /// deba@1750: /// Find the connected components of an undirected graph. deba@1750: /// deba@1763: /// \image html connected_components.png deba@1763: /// \image latex connected_components.eps "Connected components" width=\textwidth deba@1763: /// deba@1793: /// \param graph The graph. It should be undirected. deba@1793: /// \retval compMap A writable node map. The values will be set from 0 to deba@1750: /// the number of the connected components minus one. Each values of the map deba@1750: /// will be set exactly once, the values of a certain component will be deba@1750: /// set continuously. deba@1750: /// \return The number of components deba@1763: /// klao@1909: template klao@1909: int connectedComponents(const UGraph &graph, NodeMap &compMap) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::Node Node; klao@1909: typedef typename UGraph::Edge Edge; alpar@2260: checkConcept, NodeMap>(); deba@1750: deba@1750: typedef NullMap PredMap; deba@1750: typedef NullMap DistMap; deba@1750: deba@1750: int compNum = 0; klao@1909: 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(); klao@1909: for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) { deba@1750: if(!bfs.reached(n)) { deba@1750: bfs.addSource(n); deba@1750: while (!bfs.emptyQueue()) { deba@1750: compMap.set(bfs.nextNode(), compNum); deba@1750: bfs.processNextNode(); deba@1750: } deba@1750: ++compNum; deba@1750: } deba@1750: } deba@1750: return compNum; deba@1750: } deba@1750: deba@1750: namespace _topology_bits { deba@1750: deba@1750: template 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1750: /// \brief Check that the given directed graph is strongly connected. deba@1750: /// deba@1750: /// Check that the given directed graph is strongly connected. The deba@1750: /// graph is strongly connected when any two nodes of the graph are alpar@1817: /// connected with directed paths in both direction. deba@1750: /// \return %False when the graph is not strongly connected. deba@1750: /// \see connected deba@1750: /// alpar@1807: /// \note By definition, the empty graph is strongly connected. deba@1750: template deba@1750: bool stronglyConnected(const Graph& graph) { alpar@2260: checkConcept(); deba@1750: deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::NodeIt NodeIt; deba@1750: deba@2082: if (NodeIt(graph) == INVALID) return true; deba@2082: deba@1750: using namespace _topology_bits; deba@1750: deba@1750: typedef DfsVisitor 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@2429: /// \ingroup graph_prop 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@2421: /// The strongly connected components are the classes of an deba@2421: /// equivalence relation on the nodes of the graph. Two nodes are in deba@2421: /// the same class if they are connected with directed paths in both deba@2421: /// direction. deba@1750: /// deba@1793: /// \param graph The graph. deba@1750: /// \return The number of components alpar@1807: /// \note By definition, the empty graph has zero alpar@1807: /// strongly connected components. deba@1750: template deba@1750: int countStronglyConnectedComponents(const Graph& graph) { alpar@2260: 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1750: /// \brief Find the strongly connected components of a directed graph deba@1750: /// deba@2421: /// Find the strongly connected components of a directed graph. The deba@2421: /// strongly connected components are the classes of an equivalence deba@2421: /// relation on the nodes of the graph. Two nodes are in deba@2421: /// relationship when there are directed paths between them in both deba@2421: /// direction. In addition, the numbering of components will satisfy deba@2421: /// that there is no edge going from a higher numbered component to deba@2421: /// a lower. deba@1750: /// deba@1763: /// \image html strongly_connected_components.png deba@1763: /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth deba@1763: /// deba@1793: /// \param graph The graph. deba@1793: /// \retval compMap A writable node map. The values will be set from 0 to deba@2421: /// the number of the strongly connected components minus one. Each value 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) { alpar@2260: checkConcept(); deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::NodeIt NodeIt; alpar@2260: 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1750: /// \brief Find the cut edges of the strongly connected components. deba@1750: /// deba@1750: /// Find the cut edges of the strongly connected components. deba@1750: /// The strongly connected components are the classes of an equivalence deba@1750: /// relation on the nodes of the graph. Two nodes are in relationship deba@1750: /// when there are directed paths between them in both direction. deba@1750: /// The strongly connected components are separated by the cut edges. deba@1750: /// deba@1793: /// \param graph The graph. deba@1793: /// \retval cutMap A writable node map. The values will be set true when the deba@1793: /// edge is a cut edge. deba@1750: /// deba@1750: /// \return The number of cut edges deba@1750: template deba@1750: int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { alpar@2260: checkConcept(); deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::Edge Edge; deba@1750: typedef typename Graph::NodeIt NodeIt; alpar@2260: 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@1800: class CountBiNodeConnectedComponentsVisitor : public DfsVisitor { deba@1698: public: deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::Edge Edge; klao@1909: typedef typename Graph::UEdge UEdge; deba@1698: deba@1800: CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum) deba@1750: : _graph(graph), _compNum(compNum), deba@1750: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@1750: deba@1750: void start(const Node& node) { deba@1750: _predMap.set(node, INVALID); deba@1750: } deba@1750: deba@1750: void reach(const Node& node) { deba@1750: _numMap.set(node, _num); deba@1750: _retMap.set(node, _num); deba@1750: ++_num; deba@1750: } deba@1750: deba@1750: void discover(const Edge& edge) { deba@1750: _predMap.set(_graph.target(edge), _graph.source(edge)); deba@1750: } deba@1750: deba@1750: void examine(const Edge& edge) { deba@1750: if (_graph.source(edge) == _graph.target(edge) && deba@1750: _graph.direction(edge)) { deba@1750: ++_compNum; deba@1750: return; deba@1750: } deba@1750: if (_predMap[_graph.source(edge)] == _graph.target(edge)) { deba@1750: return; deba@1750: } deba@1750: if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) { deba@1750: _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]); deba@1698: } deba@1698: } deba@1698: deba@1750: void backtrack(const Edge& edge) { deba@1750: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@1750: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@1750: } deba@1750: if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) { deba@1750: ++_compNum; deba@1750: } deba@1750: } deba@1750: deba@1750: private: deba@1750: const Graph& _graph; deba@1750: int& _compNum; deba@1750: deba@1750: typename Graph::template NodeMap _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@1800: class BiNodeConnectedComponentsVisitor : public DfsVisitor { deba@1750: public: deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::Edge Edge; klao@1909: typedef typename Graph::UEdge UEdge; deba@1750: deba@1800: BiNodeConnectedComponentsVisitor(const Graph& graph, deba@1750: EdgeMap& compMap, int &compNum) deba@1750: : _graph(graph), _compMap(compMap), _compNum(compNum), deba@1750: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@1750: deba@1750: void start(const Node& node) { deba@1750: _predMap.set(node, INVALID); deba@1750: } deba@1750: deba@1750: void reach(const Node& node) { deba@1750: _numMap.set(node, _num); deba@1750: _retMap.set(node, _num); deba@1750: ++_num; deba@1750: } deba@1750: deba@1750: void discover(const Edge& edge) { deba@1750: Node target = _graph.target(edge); deba@1750: _predMap.set(target, edge); deba@1750: _edgeStack.push(edge); deba@1750: } deba@1750: deba@1750: void examine(const Edge& edge) { deba@1750: Node source = _graph.source(edge); deba@1750: Node target = _graph.target(edge); deba@1750: if (source == target && _graph.direction(edge)) { deba@1750: _compMap.set(edge, _compNum); deba@1750: ++_compNum; deba@1750: return; deba@1750: } deba@1750: if (_numMap[target] < _numMap[source]) { deba@1750: if (_predMap[source] != _graph.oppositeEdge(edge)) { deba@1750: _edgeStack.push(edge); deba@1750: } deba@1750: } deba@1750: if (_predMap[source] != INVALID && deba@1750: target == _graph.source(_predMap[source])) { deba@1750: return; deba@1750: } deba@1750: if (_retMap[source] > _numMap[target]) { deba@1750: _retMap.set(source, _numMap[target]); deba@1750: } deba@1750: } deba@1750: deba@1750: void backtrack(const Edge& edge) { deba@1750: Node source = _graph.source(edge); deba@1750: Node target = _graph.target(edge); deba@1750: if (_retMap[source] > _retMap[target]) { deba@1750: _retMap.set(source, _retMap[target]); deba@1750: } deba@1750: if (_numMap[source] <= _retMap[target]) { deba@1750: while (_edgeStack.top() != edge) { deba@1750: _compMap.set(_edgeStack.top(), _compNum); deba@1750: _edgeStack.pop(); deba@1750: } deba@1750: _compMap.set(edge, _compNum); deba@1750: _edgeStack.pop(); deba@1750: ++_compNum; deba@1750: } deba@1750: } deba@1750: deba@1750: private: deba@1750: const Graph& _graph; deba@1750: EdgeMap& _compMap; deba@1750: int& _compNum; deba@1750: deba@1750: typename Graph::template NodeMap _numMap; deba@1750: typename Graph::template NodeMap _retMap; deba@1750: typename Graph::template NodeMap _predMap; klao@1909: std::stack _edgeStack; deba@1750: int _num; deba@1750: }; deba@1750: deba@1750: deba@1750: template deba@1800: class BiNodeConnectedCutNodesVisitor : public DfsVisitor { deba@1750: public: deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::Edge Edge; klao@1909: typedef typename Graph::UEdge UEdge; deba@1750: deba@1800: BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap, deba@1750: int& cutNum) deba@1750: : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), deba@1750: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@1750: deba@1750: void start(const Node& node) { deba@1750: _predMap.set(node, INVALID); deba@1750: rootCut = false; deba@1750: } deba@1750: deba@1750: void reach(const Node& node) { deba@1750: _numMap.set(node, _num); deba@1750: _retMap.set(node, _num); deba@1750: ++_num; deba@1750: } deba@1750: deba@1750: void discover(const Edge& edge) { deba@1750: _predMap.set(_graph.target(edge), _graph.source(edge)); deba@1750: } deba@1750: deba@1750: void examine(const Edge& edge) { deba@1750: if (_graph.source(edge) == _graph.target(edge) && deba@1750: _graph.direction(edge)) { deba@1750: if (!_cutMap[_graph.source(edge)]) { deba@1750: _cutMap.set(_graph.source(edge), true); deba@1750: ++_cutNum; deba@1750: } deba@1750: return; deba@1750: } deba@1750: if (_predMap[_graph.source(edge)] == _graph.target(edge)) return; deba@1750: if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) { deba@1750: _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]); deba@1750: } deba@1750: } deba@1750: deba@1750: void backtrack(const Edge& edge) { deba@1750: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@1750: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@1750: } deba@1750: if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) { deba@1750: if (_predMap[_graph.source(edge)] != INVALID) { deba@1750: if (!_cutMap[_graph.source(edge)]) { deba@1750: _cutMap.set(_graph.source(edge), true); deba@1750: ++_cutNum; deba@1750: } deba@1750: } else if (rootCut) { deba@1750: if (!_cutMap[_graph.source(edge)]) { deba@1750: _cutMap.set(_graph.source(edge), true); deba@1750: ++_cutNum; deba@1750: } deba@1750: } else { deba@1750: rootCut = true; deba@1750: } deba@1750: } deba@1750: } deba@1750: deba@1750: private: deba@1750: const Graph& _graph; deba@1750: NodeMap& _cutMap; deba@1750: int& _cutNum; deba@1750: deba@1750: typename Graph::template NodeMap _numMap; deba@1750: typename Graph::template NodeMap _retMap; deba@1750: typename Graph::template NodeMap _predMap; klao@1909: std::stack _edgeStack; deba@1750: int _num; deba@1750: bool rootCut; deba@1750: }; deba@1750: deba@1750: } deba@1750: klao@1909: template klao@1909: int countBiNodeConnectedComponents(const UGraph& graph); deba@1750: deba@2429: /// \ingroup graph_prop 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. klao@1909: template klao@1909: bool biNodeConnected(const UGraph& graph) { deba@1800: return countBiNodeConnectedComponents(graph) == 1; deba@1750: } deba@1750: deba@2429: /// \ingroup graph_prop deba@1750: /// deba@1750: /// \brief Count the biconnected components. deba@1750: /// deba@1767: /// This function finds the bi-node-connected components in an undirected deba@1750: /// graph. The biconnected components are the classes of an equivalence deba@1750: /// relation on the undirected edges. Two undirected edge is in relationship deba@1750: /// when they are on same circle. deba@1750: /// deba@1750: /// \param graph The graph. deba@1750: /// \return The number of components. klao@1909: template klao@1909: int countBiNodeConnectedComponents(const UGraph& graph) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::NodeIt NodeIt; deba@1750: deba@1750: using namespace _topology_bits; deba@1750: klao@1909: typedef CountBiNodeConnectedComponentsVisitor Visitor; deba@1750: deba@1750: int compNum = 0; deba@1750: Visitor visitor(graph, compNum); deba@1750: klao@1909: 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1767: /// \brief Find the bi-node-connected components. deba@1750: /// deba@1767: /// This function finds the bi-node-connected components in an undirected deba@1767: /// graph. The bi-node-connected components are the classes of an equivalence deba@1750: /// relation on the undirected edges. Two undirected edge are in relationship deba@1750: /// when they are on same circle. deba@1750: /// deba@1763: /// \image html node_biconnected_components.png deba@1767: /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth deba@1763: /// deba@1750: /// \param graph The graph. klao@1909: /// \retval compMap A writable uedge map. The values will be set from 0 deba@1793: /// to the number of the biconnected components minus one. Each values deba@1750: /// of the map will be set exactly once, the values of a certain component deba@1750: /// will be set continuously. deba@1750: /// \return The number of components. deba@1763: /// klao@1909: template klao@1909: int biNodeConnectedComponents(const UGraph& graph, klao@1909: UEdgeMap& compMap) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::NodeIt NodeIt; klao@1909: typedef typename UGraph::UEdge UEdge; alpar@2260: checkConcept, UEdgeMap>(); deba@1750: deba@1750: using namespace _topology_bits; deba@1750: klao@1909: typedef BiNodeConnectedComponentsVisitor Visitor; deba@1750: deba@1750: int compNum = 0; deba@1750: Visitor visitor(graph, compMap, compNum); deba@1750: klao@1909: 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1767: /// \brief Find the bi-node-connected cut nodes. deba@1750: /// deba@1767: /// This function finds the bi-node-connected cut nodes in an undirected deba@1767: /// graph. The bi-node-connected components are the classes of an equivalence deba@1750: /// relation on the undirected edges. Two undirected edges are in deba@1750: /// relationship when they are on same circle. The biconnected components deba@1750: /// are separted by nodes which are the cut nodes of the components. deba@1750: /// deba@1750: /// \param graph The graph. deba@1793: /// \retval cutMap A writable edge map. The values will be set true when deba@1750: /// the node separate two or more components. deba@1750: /// \return The number of the cut nodes. klao@1909: template klao@1909: int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::Node Node; klao@1909: typedef typename UGraph::NodeIt NodeIt; alpar@2260: checkConcept, NodeMap>(); deba@1750: deba@1750: using namespace _topology_bits; deba@1750: klao@1909: typedef BiNodeConnectedCutNodesVisitor Visitor; deba@1750: deba@1750: int cutNum = 0; deba@1750: Visitor visitor(graph, cutMap, cutNum); deba@1750: klao@1909: 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@1800: class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor { deba@1750: public: deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::Edge Edge; klao@1909: typedef typename Graph::UEdge UEdge; deba@1750: deba@1800: CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum) deba@1750: : _graph(graph), _compNum(compNum), deba@1750: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@1750: deba@1750: void start(const Node& node) { deba@1750: _predMap.set(node, INVALID); deba@1750: } deba@1750: deba@1750: void reach(const Node& node) { deba@1750: _numMap.set(node, _num); deba@1750: _retMap.set(node, _num); deba@1750: ++_num; deba@1750: } deba@1750: deba@1750: void leave(const Node& node) { deba@1750: if (_numMap[node] <= _retMap[node]) { deba@1750: ++_compNum; deba@1750: } deba@1750: } deba@1750: deba@1750: void discover(const Edge& edge) { deba@1750: _predMap.set(_graph.target(edge), edge); deba@1750: } deba@1750: deba@1750: void examine(const Edge& edge) { deba@1750: if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) { deba@1750: return; deba@1750: } deba@1750: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@1750: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@1750: } deba@1750: } deba@1750: deba@1750: void backtrack(const Edge& edge) { deba@1750: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@1750: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@1750: } deba@1750: } deba@1750: deba@1750: private: deba@1750: const Graph& _graph; deba@1750: int& _compNum; deba@1750: deba@1750: typename Graph::template NodeMap _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@1800: class BiEdgeConnectedComponentsVisitor : public DfsVisitor { deba@1750: public: deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::Edge Edge; klao@1909: typedef typename Graph::UEdge UEdge; deba@1750: deba@1800: BiEdgeConnectedComponentsVisitor(const Graph& graph, deba@1750: NodeMap& compMap, int &compNum) deba@1750: : _graph(graph), _compMap(compMap), _compNum(compNum), deba@1750: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@1750: deba@1750: void start(const Node& node) { deba@1750: _predMap.set(node, INVALID); deba@1750: } deba@1750: deba@1750: void reach(const Node& node) { deba@1750: _numMap.set(node, _num); deba@1750: _retMap.set(node, _num); deba@1750: _nodeStack.push(node); deba@1750: ++_num; deba@1750: } deba@1750: deba@1750: void leave(const Node& node) { deba@1750: if (_numMap[node] <= _retMap[node]) { deba@1750: while (_nodeStack.top() != node) { deba@1750: _compMap.set(_nodeStack.top(), _compNum); deba@1750: _nodeStack.pop(); deba@1750: } deba@1750: _compMap.set(node, _compNum); deba@1750: _nodeStack.pop(); deba@1750: ++_compNum; deba@1750: } deba@1750: } deba@1750: deba@1750: void discover(const Edge& edge) { deba@1750: _predMap.set(_graph.target(edge), edge); deba@1750: } deba@1750: deba@1750: void examine(const Edge& edge) { deba@1750: if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) { deba@1750: return; deba@1750: } deba@1750: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@1750: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@1750: } deba@1750: } deba@1750: deba@1750: void backtrack(const Edge& edge) { deba@1750: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@1750: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@1750: } deba@1750: } deba@1750: deba@1750: private: deba@1750: const Graph& _graph; deba@1750: NodeMap& _compMap; deba@1750: int& _compNum; deba@1750: deba@1750: typename Graph::template NodeMap _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@1800: class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor { deba@1750: public: deba@1750: typedef typename Graph::Node Node; deba@1750: typedef typename Graph::Edge Edge; klao@1909: typedef typename Graph::UEdge UEdge; deba@1750: deba@1800: BiEdgeConnectedCutEdgesVisitor(const Graph& graph, deba@1750: EdgeMap& cutMap, int &cutNum) deba@1750: : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), deba@1750: _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} deba@1750: deba@1750: void start(const Node& node) { deba@1750: _predMap[node] = INVALID; deba@1750: } deba@1750: deba@1750: void reach(const Node& node) { deba@1750: _numMap.set(node, _num); deba@1750: _retMap.set(node, _num); deba@1750: ++_num; deba@1750: } deba@1750: deba@1750: void leave(const Node& node) { deba@1750: if (_numMap[node] <= _retMap[node]) { deba@1750: if (_predMap[node] != INVALID) { deba@1750: _cutMap.set(_predMap[node], true); deba@1750: ++_cutNum; deba@1750: } deba@1750: } deba@1750: } deba@1750: deba@1750: void discover(const Edge& edge) { deba@1750: _predMap.set(_graph.target(edge), edge); deba@1750: } deba@1750: deba@1750: void examine(const Edge& edge) { deba@1750: if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) { deba@1750: return; deba@1750: } deba@1750: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@1750: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@1750: } deba@1750: } deba@1750: deba@1750: void backtrack(const Edge& edge) { deba@1750: if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { deba@1750: _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); deba@1750: } deba@1750: } deba@1750: deba@1750: private: deba@1750: const Graph& _graph; deba@1750: EdgeMap& _cutMap; deba@1750: int& _cutNum; deba@1750: deba@1750: typename Graph::template NodeMap _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: klao@1909: template deba@2421: int countBiEdgeConnectedComponents(const UGraph& graph); deba@1750: deba@2429: /// \ingroup graph_prop 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. klao@1909: template klao@1909: bool biEdgeConnected(const UGraph& graph) { deba@1800: return countBiEdgeConnectedComponents(graph) == 1; deba@1750: } deba@1750: deba@2429: /// \ingroup graph_prop deba@1750: /// deba@1767: /// \brief Count the bi-edge-connected components. deba@1750: /// deba@1767: /// This function count the bi-edge-connected components in an undirected deba@1767: /// graph. The bi-edge-connected components are the classes of an equivalence deba@1750: /// relation on the nodes. Two nodes are in relationship when they are deba@1750: /// connected with at least two edge-disjoint paths. deba@1750: /// deba@1750: /// \param graph The undirected graph. deba@1750: /// \return The number of components. klao@1909: template klao@1909: int countBiEdgeConnectedComponents(const UGraph& graph) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::NodeIt NodeIt; deba@1750: deba@1750: using namespace _topology_bits; deba@1750: klao@1909: typedef CountBiEdgeConnectedComponentsVisitor Visitor; deba@1750: deba@1750: int compNum = 0; deba@1750: Visitor visitor(graph, compNum); deba@1750: klao@1909: 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1767: /// \brief Find the bi-edge-connected components. deba@1750: /// deba@1767: /// This function finds the bi-edge-connected components in an undirected deba@1767: /// graph. The bi-edge-connected components are the classes of an equivalence deba@1750: /// relation on the nodes. Two nodes are in relationship when they are deba@1750: /// connected at least two edge-disjoint paths. deba@1750: /// deba@1763: /// \image html edge_biconnected_components.png deba@1767: /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth deba@1763: /// deba@1750: /// \param graph The graph. deba@1793: /// \retval compMap A writable node map. The values will be set from 0 to deba@1750: /// the number of the biconnected components minus one. Each values deba@1750: /// of the map will be set exactly once, the values of a certain component deba@1750: /// will be set continuously. deba@1750: /// \return The number of components. deba@1763: /// klao@1909: template klao@1909: int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::NodeIt NodeIt; klao@1909: typedef typename UGraph::Node Node; alpar@2260: checkConcept, NodeMap>(); deba@1750: deba@1750: using namespace _topology_bits; deba@1750: klao@1909: typedef BiEdgeConnectedComponentsVisitor Visitor; deba@1750: deba@1750: int compNum = 0; deba@1750: Visitor visitor(graph, compMap, compNum); deba@1750: klao@1909: 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1767: /// \brief Find the bi-edge-connected cut edges. deba@1750: /// deba@1767: /// This function finds the bi-edge-connected components in an undirected deba@1767: /// graph. The bi-edge-connected components are the classes of an equivalence deba@1750: /// relation on the nodes. Two nodes are in relationship when they are deba@1767: /// connected with at least two edge-disjoint paths. The bi-edge-connected deba@1750: /// components are separted by edges which are the cut edges of the deba@1750: /// components. deba@1750: /// deba@1750: /// \param graph The graph. deba@1793: /// \retval cutMap A writable node map. The values will be set true when the deba@1750: /// edge is a cut edge. deba@1750: /// \return The number of cut edges. klao@1909: template klao@1909: int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::NodeIt NodeIt; klao@1909: typedef typename UGraph::UEdge UEdge; alpar@2260: checkConcept, UEdgeMap>(); deba@1750: deba@1750: using namespace _topology_bits; deba@1750: klao@1909: typedef BiEdgeConnectedCutEdgesVisitor Visitor; deba@1750: deba@1750: int cutNum = 0; deba@1750: Visitor visitor(graph, cutMap, cutNum); deba@1750: klao@1909: 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1750: /// \brief Sort the nodes of a DAG into topolgical order. deba@1750: /// deba@1750: /// Sort the nodes of a DAG into topolgical order. deba@1750: /// deba@1793: /// \param graph The graph. It should be directed and acyclic. deba@1793: /// \retval order A writable node map. The values will be set from 0 to deba@1750: /// the number of the nodes in the graph minus one. Each values of the map deba@1750: /// will be set exactly once, the values will be set descending order. deba@1750: /// deba@1750: /// \see checkedTopologicalSort deba@1750: /// \see dag deba@1698: template deba@1750: void topologicalSort(const Graph& graph, NodeMap& order) { deba@1750: using namespace _topology_bits; deba@1750: alpar@2260: checkConcept(); alpar@2260: 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1750: /// \brief Sort the nodes of a DAG into topolgical order. deba@1750: /// deba@1750: /// Sort the nodes of a DAG into topolgical order. It also checks deba@1750: /// that the given graph is DAG. deba@1750: /// deba@1793: /// \param graph The graph. It should be directed and acyclic. deba@1750: /// \retval order A readable - writable node map. The values will be set deba@1750: /// from 0 to the number of the nodes in the graph minus one. Each values deba@1750: /// of the map will be set exactly once, the values will be set descending deba@1750: /// order. deba@1750: /// \return %False when the graph is not DAG. deba@1750: /// deba@1750: /// \see topologicalSort deba@1750: /// \see dag deba@1750: template deba@1750: bool checkedTopologicalSort(const Graph& graph, NodeMap& order) { deba@1698: using namespace _topology_bits; deba@1698: alpar@2260: checkConcept(); alpar@2260: 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@2429: /// \ingroup graph_prop 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: alpar@2260: 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@2429: /// \ingroup graph_prop deba@1698: /// deba@1698: /// \brief Check that the given undirected graph is acyclic. deba@1698: /// deba@1698: /// Check that the given undirected graph acyclic. deba@1750: /// \param graph The undirected graph. deba@1750: /// \return %True when there is no circle in the graph. deba@1750: /// \see dag klao@1909: template klao@1909: bool acyclic(const UGraph& graph) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::Node Node; klao@1909: typedef typename UGraph::NodeIt NodeIt; klao@1909: typedef typename UGraph::Edge Edge; klao@1909: 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@2429: /// \ingroup graph_prop deba@1750: /// deba@1698: /// \brief Check that the given undirected graph is tree. deba@1698: /// deba@1698: /// Check that the given undirected graph is tree. deba@1750: /// \param graph The undirected graph. deba@1750: /// \return %True when the graph is acyclic and connected. klao@1909: template klao@1909: bool tree(const UGraph& graph) { alpar@2260: checkConcept(); klao@1909: typedef typename UGraph::Node Node; klao@1909: typedef typename UGraph::NodeIt NodeIt; klao@1909: typedef typename UGraph::Edge Edge; klao@1909: 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@2306: namespace _topology_bits { deba@2306: deba@2306: template deba@2306: class BipartiteVisitor : public BfsVisitor { deba@2306: public: deba@2306: typedef typename Graph::Edge Edge; deba@2306: typedef typename Graph::Node Node; deba@2306: deba@2306: BipartiteVisitor(const Graph& graph, bool& bipartite) deba@2306: : _graph(graph), _part(graph), _bipartite(bipartite) {} deba@2306: deba@2306: void start(const Node& node) { deba@2306: _part[node] = true; deba@2306: } deba@2306: void discover(const Edge& edge) { deba@2306: _part.set(_graph.target(edge), !_part[_graph.source(edge)]); deba@2306: } deba@2306: void examine(const Edge& edge) { deba@2306: _bipartite = _bipartite && deba@2306: _part[_graph.target(edge)] != _part[_graph.source(edge)]; deba@2306: } deba@2306: deba@2306: private: deba@2306: deba@2306: const Graph& _graph; deba@2306: typename Graph::template NodeMap _part; deba@2306: bool& _bipartite; deba@2306: }; deba@2306: deba@2306: template deba@2306: class BipartitePartitionsVisitor : public BfsVisitor { deba@2306: public: deba@2306: typedef typename Graph::Edge Edge; deba@2306: typedef typename Graph::Node Node; deba@2306: deba@2306: BipartitePartitionsVisitor(const Graph& graph, deba@2306: PartMap& part, bool& bipartite) deba@2306: : _graph(graph), _part(part), _bipartite(bipartite) {} deba@2306: deba@2306: void start(const Node& node) { deba@2306: _part.set(node, true); deba@2306: } deba@2306: void discover(const Edge& edge) { deba@2306: _part.set(_graph.target(edge), !_part[_graph.source(edge)]); deba@2306: } deba@2306: void examine(const Edge& edge) { deba@2306: _bipartite = _bipartite && deba@2306: _part[_graph.target(edge)] != _part[_graph.source(edge)]; deba@2306: } deba@2306: deba@2306: private: deba@2306: deba@2306: const Graph& _graph; deba@2306: PartMap& _part; deba@2306: bool& _bipartite; deba@2306: }; deba@2306: } deba@2306: deba@2429: /// \ingroup graph_prop alpar@1739: /// deba@1800: /// \brief Check if the given undirected graph is bipartite or not deba@1750: /// deba@1800: /// The function checks if the given undirected \c graph graph is bipartite deba@1800: /// or not. The \ref Bfs algorithm is used to calculate the result. deba@1750: /// \param graph The undirected graph. deba@1800: /// \return %True if \c graph is bipartite, %false otherwise. deba@1800: /// \sa bipartitePartitions deba@1800: /// deba@1800: /// \author Balazs Attila Mihaly klao@1909: template klao@1909: inline bool bipartite(const UGraph &graph){ deba@2306: using namespace _topology_bits; deba@2306: alpar@2260: checkConcept(); deba@1800: klao@1909: typedef typename UGraph::NodeIt NodeIt; klao@1909: typedef typename UGraph::EdgeIt EdgeIt; deba@1800: deba@2306: bool bipartite = true; deba@2306: deba@2306: BipartiteVisitor deba@2306: visitor(graph, bipartite); deba@2306: BfsVisit > deba@2306: bfs(graph, visitor); deba@1800: bfs.init(); deba@2306: for(NodeIt it(graph); it != INVALID; ++it) { deba@2306: if(!bfs.reached(it)){ deba@2306: bfs.addSource(it); deba@2306: while (!bfs.emptyQueue()) { deba@2306: bfs.processNextNode(); deba@2306: if (!bipartite) return false; deba@2306: } deba@1800: } deba@1800: } deba@1800: return true; deba@1979: } deba@1800: deba@2429: /// \ingroup graph_prop deba@1800: /// deba@1800: /// \brief Check if the given undirected graph is bipartite or not deba@1800: /// deba@1800: /// The function checks if the given undirected graph is bipartite deba@1800: /// or not. The \ref Bfs algorithm is used to calculate the result. deba@1800: /// During the execution, the \c partMap will be set as the two deba@1800: /// partitions of the graph. deba@1800: /// \param graph The undirected graph. alpar@1808: /// \retval partMap A writable bool map of nodes. It will be set as the deba@1800: /// two partitions of the graph. deba@1800: /// \return %True if \c graph is bipartite, %false otherwise. deba@1800: /// deba@1800: /// \author Balazs Attila Mihaly deba@1800: /// deba@1800: /// \image html bipartite_partitions.png deba@1800: /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth klao@1909: template klao@1909: inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){ deba@2306: using namespace _topology_bits; deba@2306: alpar@2260: checkConcept(); deba@1800: klao@1909: typedef typename UGraph::Node Node; klao@1909: typedef typename UGraph::NodeIt NodeIt; klao@1909: typedef typename UGraph::EdgeIt EdgeIt; deba@2306: deba@2306: bool bipartite = true; deba@2306: deba@2306: BipartitePartitionsVisitor deba@2306: visitor(graph, partMap, bipartite); deba@2306: BfsVisit > deba@2306: bfs(graph, visitor); deba@1800: bfs.init(); deba@2306: for(NodeIt it(graph); it != INVALID; ++it) { deba@2306: if(!bfs.reached(it)){ deba@2306: bfs.addSource(it); deba@2306: while (!bfs.emptyQueue()) { deba@2306: bfs.processNextNode(); deba@2306: if (!bipartite) return false; deba@2306: } deba@1740: } deba@1740: } deba@2306: return true; deba@2306: } deba@2306: deba@2306: /// \brief Returns true when there is not loop edge in the graph. deba@2306: /// deba@2306: /// Returns true when there is not loop edge in the graph. deba@2306: template deba@2306: bool loopFree(const Graph& graph) { deba@2306: for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) { deba@2306: if (graph.source(it) == graph.target(it)) return false; deba@2306: } deba@2306: return true; deba@2306: } deba@2306: deba@2306: /// \brief Returns true when there is not parallel edges in the graph. deba@2306: /// deba@2306: /// Returns true when there is not parallel edges in the graph. deba@2306: template deba@2306: bool parallelFree(const Graph& graph) { deba@2306: typename Graph::template NodeMap reached(graph, false); deba@2306: for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { deba@2306: for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) { deba@2306: if (reached[graph.target(e)]) return false; deba@2306: reached.set(graph.target(e), true); deba@2306: } deba@2306: for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) { deba@2306: reached.set(graph.target(e), false); deba@2306: } deba@2306: } deba@2306: return true; deba@2306: } deba@2306: deba@2306: /// \brief Returns true when there is not loop edge and parallel deba@2306: /// edges in the graph. deba@2306: /// deba@2306: /// Returns true when there is not loop edge and parallel edges in deba@2306: /// the graph. deba@2306: template deba@2306: bool simpleGraph(const Graph& graph) { deba@2306: typename Graph::template NodeMap reached(graph, false); deba@2306: for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { deba@2306: reached.set(n, true); deba@2306: for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) { deba@2306: if (reached[graph.target(e)]) return false; deba@2306: reached.set(graph.target(e), true); deba@2306: } deba@2306: for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) { deba@2306: reached.set(graph.target(e), false); deba@2306: } deba@2306: reached.set(n, false); deba@1800: } deba@1750: return true; deba@1979: } deba@1750: deba@1698: } //namespace lemon deba@1698: deba@1698: #endif //LEMON_TOPOLOGY_H