# Changeset 1750:5c76ebbb4818 in lemon-0.x for lemon/topology.h

Ignore:
Timestamp:
11/02/05 16:23:46 (15 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2279
Message:

Connected components, etc...
Based on the dfs visitor interface

File:
1 edited

Unmodified
Added
Removed
• ## lemon/topology.h

 r1740 #include #include #include #include #include #include /// \ingroup flowalgs #include #include #include #include /// \ingroup topology /// \file /// \brief Topology related algorithms /// /// Topology related algorithms ///\todo Place the file contents is the module tree. namespace lemon { /// \ingroup topology /// /// \brief Check that the given undirected graph is connected. /// /// Check that the given undirected graph connected. /// \param graph The undirected graph. /// \return %True when there is path between any two nodes in the graph. /// \warning The empty graph is not connected. template bool connected(const UndirGraph& graph) { checkConcept(); typedef typename UndirGraph::NodeIt NodeIt; if (NodeIt(graph) == INVALID) return false; Dfs dfs(graph); dfs.run(NodeIt(graph)); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { return false; } } return true; } /// \ingroup topology /// /// \brief Count the number of connected components of an undirected graph /// /// Count the number of connected components of an undirected graph /// /// \param g The graph. In must be undirected. /// \return The number of components template int countConnectedComponents(const UndirGraph &graph) { checkConcept(); typedef typename UndirGraph::Node Node; typedef typename UndirGraph::Edge Edge; typedef NullMap PredMap; typedef NullMap DistMap; int compNum = 0; typename Bfs:: template DefPredMap:: template DefDistMap:: Create bfs(graph); PredMap predMap; bfs.predMap(predMap); DistMap distMap; bfs.distMap(distMap); bfs.init(); for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) { if (!bfs.reached(n)) { bfs.addSource(n); bfs.start(); ++compNum; } } return compNum; } /// \ingroup topology /// /// \brief Find the connected components of an undirected graph /// /// Find the connected components of an undirected graph. /// /// \param g The graph. In must be undirected. /// \retval comp A writable node map. The values will be set from 0 to /// the number of the connected components minus one. Each values of the map /// will be set exactly once, the values of a certain component will be /// set continuously. /// \return The number of components template int connectedComponents(const UndirGraph &graph, NodeMap &compMap) { checkConcept(); typedef typename UndirGraph::Node Node; typedef typename UndirGraph::Edge Edge; checkConcept, NodeMap>(); typedef NullMap PredMap; typedef NullMap DistMap; int compNum = 0; typename Bfs:: template DefPredMap:: template DefDistMap:: Create bfs(graph); PredMap predMap; bfs.predMap(predMap); DistMap distMap; bfs.distMap(distMap); bfs.init(); for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) { if(!bfs.reached(n)) { bfs.addSource(n); while (!bfs.emptyQueue()) { compMap.set(bfs.nextNode(), compNum); bfs.processNextNode(); } ++compNum; } } return compNum; } namespace _topology_bits { template class BackCounterMap { template struct LeaveOrderVisitor : public DfsVisitor { public: BackCounterMap(NodeMap& _nodeMap, int _counter) : nodeMap(_nodeMap), counter(_counter) {} void set(typename NodeMap::Key key, bool val) { if (val) { nodeMap.set(key, --counter); } else { nodeMap.set(key, -1); } } bool operator[](typename NodeMap::Key key) const { return nodeMap[key] != -1; typedef typename Graph::Node Node; LeaveOrderVisitor(Iterator it) : _it(it) {} void leave(const Node& node) { *(_it++) = node; } private: NodeMap& nodeMap; int counter; Iterator _it; }; } // \todo Its to special output // ReadWriteMap template struct FillMapVisitor : public DfsVisitor { public: typedef typename Graph::Node Node; typedef typename Map::Value Value; FillMapVisitor(Map& map, Value& value) : _map(map), _value(value) {} void reach(const Node& node) { _map.set(node, _value); } private: Map& _map; Value& _value; }; template struct StronglyConnectedCutEdgesVisitor : public DfsVisitor { public: typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap, int& cutNum) : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), _compMap(graph), _num(0) { } void stop(const Node&) { ++_num; } void reach(const Node& node) { _compMap.set(node, _num); } void examine(const Edge& edge) { if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) { _cutMap.set(edge, true); ++_cutNum; } } private: const Graph& _graph; EdgeMap& _cutMap; int& _cutNum; typename Graph::template NodeMap _compMap; int _num; }; } /// \ingroup topology /// /// \brief Check that the given directed graph is strongly connected. /// /// Check that the given directed graph is strongly connected. The /// graph is strongly connected when any two nodes of the graph are /// connected with directed pathes in both direction. /// \return %False when the graph is not strongly connected. /// \see connected /// /// \waning Empty graph is not strongly connected. template bool stronglyConnected(const Graph& graph) { checkConcept(); if (NodeIt(graph) == INVALID) return false; typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; using namespace _topology_bits; typedef DfsVisitor Visitor; Visitor visitor; DfsVisit dfs(graph, visitor); dfs.init(); dfs.addSource(NodeIt(graph)); dfs.start(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { return false; } } typedef RevGraphAdaptor RGraph; RGraph rgraph(graph); typedef DfsVisitor RVisitor; RVisitor rvisitor; DfsVisit rdfs(rgraph, rvisitor); rdfs.init(); rdfs.addSource(NodeIt(graph)); rdfs.start(); for (NodeIt it(graph); it != INVALID; ++it) { if (!rdfs.reached(it)) { return false; } } return true; } /// \ingroup topology /// /// \brief Count the strongly connected components of a directed graph /// /// Count the strongly connected components of a directed graph. /// The strongly connected components are the classes of an equivalence /// relation on the nodes of the graph. Two nodes are connected with /// directed paths in both direction. /// /// \param g The graph. /// \return The number of components template int countStronglyConnectedComponents(const Graph& graph) { checkConcept(); using namespace _topology_bits; typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::EdgeIt EdgeIt; typedef std::vector Container; typedef typename Container::iterator Iterator; Container nodes(countNodes(graph)); typedef LeaveOrderVisitor Visitor; Visitor visitor(nodes.begin()); DfsVisit dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } typedef typename Container::reverse_iterator RIterator; typedef RevGraphAdaptor RGraph; RGraph rgraph(graph); typedef DfsVisitor RVisitor; RVisitor rvisitor; DfsVisit rdfs(rgraph, rvisitor); int compNum = 0; rdfs.init(); for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { if (!rdfs.reached(*it)) { rdfs.addSource(*it); rdfs.start(); ++compNum; } } return compNum; } /// \ingroup topology /// /// \brief Find the strongly connected components of a directed graph /// /// Find the strongly connected components of a directed graph. /// The strongly connected components are the classes of an equivalence /// relation on the nodes of the graph. Two nodes are in relationship /// when there are directed paths between them in both direction. /// /// \param g The graph. /// \retval comp A writable node map. The values will be set from 0 to /// the number of the strongly connected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components template bool topological_sort(const Graph& graph, NodeMap& nodeMap) { int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) { checkConcept(); typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; checkConcept, NodeMap>(); using namespace _topology_bits; typedef std::vector Container; typedef typename Container::iterator Iterator; Container nodes(countNodes(graph)); typedef LeaveOrderVisitor Visitor; Visitor visitor(nodes.begin()); DfsVisit dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } typedef typename Container::reverse_iterator RIterator; typedef RevGraphAdaptor RGraph; RGraph rgraph(graph); int compNum = 0; typedef FillMapVisitor RVisitor; RVisitor rvisitor(compMap, compNum); DfsVisit rdfs(rgraph, rvisitor); rdfs.init(); for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { if (!rdfs.reached(*it)) { rdfs.addSource(*it); rdfs.start(); ++compNum; } } return compNum; } /// \ingroup topology /// /// \brief Find the cut edges of the strongly connected components. /// /// Find the cut edges of the strongly connected components. /// The strongly connected components are the classes of an equivalence /// relation on the nodes of the graph. Two nodes are in relationship /// when there are directed paths between them in both direction. /// The strongly connected components are separated by the cut edges. /// /// \param g The graph. /// \retval comp A writable edge map. The values will be set true when /// the edge is cut edge otherwise false. /// /// \return The number of cut edges template int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { checkConcept(); checkConcept, NodeMap>(); typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename Graph::NodeIt NodeIt; checkConcept, EdgeMap>(); using namespace _topology_bits; typedef std::vector Container; typedef typename Container::iterator Iterator; Container nodes(countNodes(graph)); typedef LeaveOrderVisitor Visitor; Visitor visitor(nodes.begin()); DfsVisit dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } typedef typename Container::reverse_iterator RIterator; typedef RevGraphAdaptor RGraph; RGraph rgraph(graph); int cutNum = 0; typedef StronglyConnectedCutEdgesVisitor RVisitor; RVisitor rvisitor(rgraph, cutMap, cutNum); DfsVisit rdfs(rgraph, rvisitor); rdfs.init(); for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { if (!rdfs.reached(*it)) { rdfs.addSource(*it); rdfs.start(); } } return cutNum; } namespace _topology_bits { template class CountNodeBiconnectedComponentsVisitor : public DfsVisitor { public: typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename Graph::UndirEdge UndirEdge; CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) : _graph(graph), _compNum(compNum), _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} void start(const Node& node) { _predMap.set(node, INVALID); } void reach(const Node& node) { _numMap.set(node, _num); _retMap.set(node, _num); ++_num; } void discover(const Edge& edge) { _predMap.set(_graph.target(edge), _graph.source(edge)); } void examine(const Edge& edge) { if (_graph.source(edge) == _graph.target(edge) && _graph.direction(edge)) { ++_compNum; return; } if (_predMap[_graph.source(edge)] == _graph.target(edge)) { return; } if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) { _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]); } } void backtrack(const Edge& edge) { if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); } if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) { ++_compNum; } } private: const Graph& _graph; int& _compNum; typename Graph::template NodeMap _numMap; typename Graph::template NodeMap _retMap; typename Graph::template NodeMap _predMap; int _num; }; template class NodeBiconnectedComponentsVisitor : public DfsVisitor { public: typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename Graph::UndirEdge UndirEdge; NodeBiconnectedComponentsVisitor(const Graph& graph, EdgeMap& compMap, int &compNum) : _graph(graph), _compMap(compMap), _compNum(compNum), _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} void start(const Node& node) { _predMap.set(node, INVALID); } void reach(const Node& node) { _numMap.set(node, _num); _retMap.set(node, _num); ++_num; } void discover(const Edge& edge) { Node target = _graph.target(edge); _predMap.set(target, edge); _edgeStack.push(edge); } void examine(const Edge& edge) { Node source = _graph.source(edge); Node target = _graph.target(edge); if (source == target && _graph.direction(edge)) { _compMap.set(edge, _compNum); ++_compNum; return; } if (_numMap[target] < _numMap[source]) { if (_predMap[source] != _graph.oppositeEdge(edge)) { _edgeStack.push(edge); } } if (_predMap[source] != INVALID && target == _graph.source(_predMap[source])) { return; } if (_retMap[source] > _numMap[target]) { _retMap.set(source, _numMap[target]); } } void backtrack(const Edge& edge) { Node source = _graph.source(edge); Node target = _graph.target(edge); if (_retMap[source] > _retMap[target]) { _retMap.set(source, _retMap[target]); } if (_numMap[source] <= _retMap[target]) { while (_edgeStack.top() != edge) { _compMap.set(_edgeStack.top(), _compNum); _edgeStack.pop(); } _compMap.set(edge, _compNum); _edgeStack.pop(); ++_compNum; } } private: const Graph& _graph; EdgeMap& _compMap; int& _compNum; typename Graph::template NodeMap _numMap; typename Graph::template NodeMap _retMap; typename Graph::template NodeMap _predMap; std::stack _edgeStack; int _num; }; template class NodeBiconnectedCutNodesVisitor : public DfsVisitor { public: typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename Graph::UndirEdge UndirEdge; NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap, int& cutNum) : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} void start(const Node& node) { _predMap.set(node, INVALID); rootCut = false; } void reach(const Node& node) { _numMap.set(node, _num); _retMap.set(node, _num); ++_num; } void discover(const Edge& edge) { _predMap.set(_graph.target(edge), _graph.source(edge)); } void examine(const Edge& edge) { if (_graph.source(edge) == _graph.target(edge) && _graph.direction(edge)) { if (!_cutMap[_graph.source(edge)]) { _cutMap.set(_graph.source(edge), true); ++_cutNum; } return; } if (_predMap[_graph.source(edge)] == _graph.target(edge)) return; if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) { _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]); } } void backtrack(const Edge& edge) { if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); } if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) { if (_predMap[_graph.source(edge)] != INVALID) { if (!_cutMap[_graph.source(edge)]) { _cutMap.set(_graph.source(edge), true); ++_cutNum; } } else if (rootCut) { if (!_cutMap[_graph.source(edge)]) { _cutMap.set(_graph.source(edge), true); ++_cutNum; } } else { rootCut = true; } } } private: const Graph& _graph; NodeMap& _cutMap; int& _cutNum; typename Graph::template NodeMap _numMap; typename Graph::template NodeMap _retMap; typename Graph::template NodeMap _predMap; std::stack _edgeStack; int _num; bool rootCut; }; } template int countNodeBiconnectedComponents(const UndirGraph& graph); /// \ingroup topology /// /// \brief Checks the graph is node biconnected. /// /// This function checks that the undirected graph is node biconnected /// graph. The graph is node biconnected if any two undirected edge is /// on same circle. /// /// \param graph The graph. /// \return %True when the graph node biconnected. /// \todo Make it faster. template bool nodeBiconnected(const UndirGraph& graph) { return countNodeBiconnectedComponents(graph) == 1; } /// \ingroup topology /// /// \brief Count the biconnected components. /// /// This function finds the node biconnected components in an undirected /// graph. The biconnected components are the classes of an equivalence /// relation on the undirected edges. Two undirected edge is in relationship /// when they are on same circle. /// /// \param graph The graph. /// \return The number of components. template int countNodeBiconnectedComponents(const UndirGraph& graph) { checkConcept(); typedef typename UndirGraph::NodeIt NodeIt; using namespace _topology_bits; typedef CountNodeBiconnectedComponentsVisitor Visitor; int compNum = 0; Visitor visitor(graph, compNum); DfsVisit dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } return compNum; } /// \ingroup topology /// /// \brief Find the node biconnected components. /// /// This function finds the node biconnected components in an undirected /// graph. The node biconnected components are the classes of an equivalence /// relation on the undirected edges. Two undirected edge are in relationship /// when they are on same circle. /// /// \param graph The graph. /// \retval comp A writable undir edge map. The values will be set from 0 to /// the number of the biconnected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components. template int nodeBiconnectedComponents(const UndirGraph& graph, UndirEdgeMap& compMap) { checkConcept(); typedef typename UndirGraph::NodeIt NodeIt; typedef typename UndirGraph::UndirEdge UndirEdge; checkConcept, UndirEdgeMap>(); using namespace _topology_bits; typedef NodeBiconnectedComponentsVisitor Visitor; int compNum = 0; Visitor visitor(graph, compMap, compNum); DfsVisit dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } return compNum; } /// \ingroup topology /// /// \brief Find the node biconnected cut nodes. /// /// This function finds the node biconnected cut nodes in an undirected /// graph. The node biconnected components are the classes of an equivalence /// relation on the undirected edges. Two undirected edges are in /// relationship when they are on same circle. The biconnected components /// are separted by nodes which are the cut nodes of the components. /// /// \param graph The graph. /// \retval comp A writable edge map. The values will be set true when /// the node separate two or more components. /// \return The number of the cut nodes. template int nodeBiconnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) { checkConcept(); typedef typename UndirGraph::Node Node; typedef typename UndirGraph::NodeIt NodeIt; checkConcept, NodeMap>(); using namespace _topology_bits; typedef NodeBiconnectedCutNodesVisitor Visitor; int cutNum = 0; Visitor visitor(graph, cutMap, cutNum); DfsVisit dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } return cutNum; } namespace _topology_bits { template class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor { public: typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename Graph::UndirEdge UndirEdge; CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) : _graph(graph), _compNum(compNum), _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} void start(const Node& node) { _predMap.set(node, INVALID); } void reach(const Node& node) { _numMap.set(node, _num); _retMap.set(node, _num); ++_num; } void leave(const Node& node) { if (_numMap[node] <= _retMap[node]) { ++_compNum; } } void discover(const Edge& edge) { _predMap.set(_graph.target(edge), edge); } void examine(const Edge& edge) { if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) { return; } if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); } } void backtrack(const Edge& edge) { if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); } } private: const Graph& _graph; int& _compNum; typename Graph::template NodeMap _numMap; typename Graph::template NodeMap _retMap; typename Graph::template NodeMap _predMap; int _num; }; template class EdgeBiconnectedComponentsVisitor : public DfsVisitor { public: typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename Graph::UndirEdge UndirEdge; EdgeBiconnectedComponentsVisitor(const Graph& graph, NodeMap& compMap, int &compNum) : _graph(graph), _compMap(compMap), _compNum(compNum), _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} void start(const Node& node) { _predMap.set(node, INVALID); } void reach(const Node& node) { _numMap.set(node, _num); _retMap.set(node, _num); _nodeStack.push(node); ++_num; } void leave(const Node& node) { if (_numMap[node] <= _retMap[node]) { while (_nodeStack.top() != node) { _compMap.set(_nodeStack.top(), _compNum); _nodeStack.pop(); } _compMap.set(node, _compNum); _nodeStack.pop(); ++_compNum; } } void discover(const Edge& edge) { _predMap.set(_graph.target(edge), edge); } void examine(const Edge& edge) { if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) { return; } if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); } } void backtrack(const Edge& edge) { if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); } } private: const Graph& _graph; NodeMap& _compMap; int& _compNum; typename Graph::template NodeMap _numMap; typename Graph::template NodeMap _retMap; typename Graph::template NodeMap _predMap; std::stack _nodeStack; int _num; }; template class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor { public: typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename Graph::UndirEdge UndirEdge; EdgeBiconnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap, int &cutNum) : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} void start(const Node& node) { _predMap[node] = INVALID; } void reach(const Node& node) { _numMap.set(node, _num); _retMap.set(node, _num); ++_num; } void leave(const Node& node) { if (_numMap[node] <= _retMap[node]) { if (_predMap[node] != INVALID) { _cutMap.set(_predMap[node], true); ++_cutNum; } } } void discover(const Edge& edge) { _predMap.set(_graph.target(edge), edge); } void examine(const Edge& edge) { if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) { return; } if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); } } void backtrack(const Edge& edge) { if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); } } private: const Graph& _graph; EdgeMap& _cutMap; int& _cutNum; typename Graph::template NodeMap _numMap; typename Graph::template NodeMap _retMap; typename Graph::template NodeMap _predMap; int _num; }; } template int countEdgeBiconnectedComponents(const UndirGraph& graph); /// \ingroup topology /// /// \brief Checks that the graph is edge biconnected. /// /// This function checks that the graph is edge biconnected. The undirected /// graph is edge biconnected when any two nodes are connected with two /// edge-disjoint paths. /// /// \param graph The undirected graph. /// \return The number of components. /// \todo Make it faster. template bool edgeBiconnected(const UndirGraph& graph) { return countEdgeBiconnectedComponents(graph) == 1; } /// \ingroup topology /// /// \brief Count the edge biconnected components. /// /// This function count the edge biconnected components in an undirected /// graph. The edge biconnected components are the classes of an equivalence /// relation on the nodes. Two nodes are in relationship when they are /// connected with at least two edge-disjoint paths. /// /// \param graph The undirected graph. /// \return The number of components. template int countEdgeBiconnectedComponents(const UndirGraph& graph) { checkConcept(); typedef typename UndirGraph::NodeIt NodeIt; using namespace _topology_bits; typedef CountEdgeBiconnectedComponentsVisitor Visitor; int compNum = 0; Visitor visitor(graph, compNum); DfsVisit dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } return compNum; } /// \ingroup topology /// /// \brief Find the edge biconnected components. /// /// This function finds the edge biconnected components in an undirected /// graph. The edge biconnected components are the classes of an equivalence /// relation on the nodes. Two nodes are in relationship when they are /// connected at least two edge-disjoint paths. /// /// \param graph The graph. /// \retval comp A writable node map. The values will be set from 0 to /// the number of the biconnected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components. template int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) { checkConcept(); typedef typename UndirGraph::NodeIt NodeIt; typedef typename UndirGraph::Node Node; checkConcept, NodeMap>(); using namespace _topology_bits; typedef EdgeBiconnectedComponentsVisitor Visitor; int compNum = 0; Visitor visitor(graph, compMap, compNum); DfsVisit dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } return compNum; } /// \ingroup topology /// /// \brief Find the edge biconnected cut edges. /// /// This function finds the edge biconnected components in an undirected /// graph. The edge biconnected components are the classes of an equivalence /// relation on the nodes. Two nodes are in relationship when they are /// connected with at least two edge-disjoint paths. The edge biconnected /// components are separted by edges which are the cut edges of the /// components. /// /// \param graph The graph. /// \retval comp A writable node map. The values will be set true when the /// edge is a cut edge. /// \return The number of cut edges. template int edgeBiconnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { checkConcept(); typedef typename UndirGraph::NodeIt NodeIt; typedef typename UndirGraph::UndirEdge UndirEdge; checkConcept, UndirEdgeMap>(); using namespace _topology_bits; typedef EdgeBiconnectedCutEdgesVisitor Visitor; int cutNum = 0; Visitor visitor(graph, cutMap, cutNum); DfsVisit dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } return cutNum; } namespace _topology_bits { template class TopologicalSortVisitor : public DfsVisitor { public: typedef typename Graph::Node Node; typedef typename Graph::Edge edge; TopologicalSortVisitor(IntNodeMap& order, int num) : _order(order), _num(num) {} void leave(const Node& node) { _order.set(node, --_num); } private: IntNodeMap& _order; int _num; }; } /// \ingroup topology /// /// \brief Sort the nodes of a DAG into topolgical order. /// /// Sort the nodes of a DAG into topolgical order. /// /// \param g The graph. In must be directed and acyclic. /// \retval comp A writable node map. The values will be set from 0 to /// the number of the nodes in the graph minus one. Each values of the map /// will be set exactly once, the values  will be set descending order. /// /// \see checkedTopologicalSort /// \see dag template void topologicalSort(const Graph& graph, NodeMap& order) { using namespace _topology_bits; checkConcept(); checkConcept, NodeMap>(); typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef BackCounterMap ProcessedMap; TopologicalSortVisitor visitor(order, countNodes(graph)); DfsVisit > dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } } /// \ingroup topology /// /// \brief Sort the nodes of a DAG into topolgical order. /// /// Sort the nodes of a DAG into topolgical order. It also checks /// that the given graph is DAG. /// /// \param g The graph. In must be directed and acyclic. /// \retval order A readable - writable node map. The values will be set /// from 0 to the number of the nodes in the graph minus one. Each values /// of the map will be set exactly once, the values will be set descending /// order. /// \return %False when the graph is not DAG. /// /// \see topologicalSort /// \see dag template bool checkedTopologicalSort(const Graph& graph, NodeMap& order) { using namespace _topology_bits; checkConcept(); checkConcept, NodeMap>(); typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Edge Edge; order = constMap(); TopologicalSortVisitor visitor(order, countNodes(graph)); DfsVisit > dfs(graph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); while (!dfs.emptyQueue()) { Edge edge = dfs.nextEdge(); Node target = graph.target(edge); if (dfs.reached(target) && order[target] == -1) { return false; } dfs.processNextEdge(); } } } return true; } /// \ingroup topology /// /// \brief Check that the given directed graph is a DAG. /// /// Check that the given directed graph is a DAG. The DAG is /// an Directed Acyclic Graph. /// \return %False when the graph is not DAG. /// \see acyclic template bool dag(const Graph& graph) { checkConcept(); typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Edge Edge; typedef typename Graph::template NodeMap ProcessedMap; typename Dfs::template DefProcessedMap:: Create dfs(graph); ProcessedMap processed(nodeMap, countNodes(graph)); ProcessedMap processed(graph); dfs.processedMap(processed); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { } /// \brief Check that the given graph is a DAG. /// /// Check that the given graph is a DAG. The DAG is /// an Directed Acyclic Graph. template bool dag(const Graph& graph) { checkConcept(); typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Edge Edge; typedef typename Graph::template NodeMap ProcessedMap; typename Dfs::template DefProcessedMap:: Create dfs(graph); ProcessedMap processed(graph); dfs.processedMap(processed); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); while (!dfs.emptyQueue()) { Edge edge = dfs.nextEdge(); Node target = graph.target(edge); if (dfs.reached(target) && !processed[target]) { return false; } dfs.processNextEdge(); } } } return true; } // UndirGraph algorithms /// \brief Check that the given undirected graph is connected. /// /// Check that the given undirected graph connected. template bool connected(const UndirGraph& graph) { checkConcept(); typedef typename UndirGraph::NodeIt NodeIt; if (NodeIt(graph) == INVALID) return false; Dfs dfs(graph); dfs.run(NodeIt(graph)); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { return false; } } return true; } /// \ingroup topology /// /// \brief Check that the given undirected graph is acyclic. /// /// Check that the given undirected graph acyclic. /// \param graph The undirected graph. /// \return %True when there is no circle in the graph. /// \see dag template bool acyclic(const UndirGraph& graph) { } /// \ingroup topology /// /// \brief Check that the given undirected graph is tree. /// /// Check that the given undirected graph is tree. /// \param graph The undirected graph. /// \return %True when the graph is acyclic and connected. template bool tree(const UndirGraph& graph) { typedef typename UndirGraph::NodeIt NodeIt; typedef typename UndirGraph::Edge Edge; if (NodeIt(graph) == INVALID) return false; Dfs dfs(graph); dfs.init(); return true; } ///Count the number of connected components of an undirected graph ///Count the number of connected components of an undirected graph /// ///\param g The graph. In must be undirected. ///\return The number of components template int countConnectedComponents(const UndirGraph &g) { /// \ingroup topology /// /// \brief Check that the given undirected graph is bipartite. /// /// Check that the given undirected graph is bipartite. /// \param graph The undirected graph. /// \return %True when the nodes can be separated into two sets that /// there are not connected nodes in neither sets. template bool bipartite(const UndirGraph& graph) { checkConcept(); int c = 0; Bfs bfs(g); bfs.init(); for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) { if(!bfs.reached(n)) { bfs.addSource(n); bfs.start(); ++c; } } return c; } ///Find the connected components of an undirected graph ///Find the connected components of an undirected graph /// ///\param g The graph. In must be undirected. ///\retval comp A writable node map. The values will be set from 0 to ///the number of the connected components minus one. Each values of the map ///will be set exactly once, the values of a certain component will be ///set continuously. ///\return The number of components ///\todo Test required template int connectedComponents(const UndirGraph &g, IntNodeMap &comp) { checkConcept(); checkConcept, IntNodeMap>(); int c = 0; Bfs bfs(g); bfs.init(); for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) { if(!bfs.reached(n)) { bfs.addSource(n); while (!bfs.emptyQueue()) { comp[bfs.nextNode()] = c; bfs.processNextNode(); } ++c; } } return c; } namespace _components_bits { template struct FillWriteMap : public MapBase { public: FillWriteMap(IntMap& _map, int& _comp) : map(_map), comp(_comp) {} void set(Key key, bool value) { if (value) { map.set(key, comp); } } private: IntMap& map; int& comp; }; template > struct BackInserterWriteMap : public MapBase { public: BackInserterWriteMap(Container& _container) : container(_container) {} void set(Key key, bool value) { if (value) { container.push_back(key); } } private: Container& container; }; } /// \brief Count the strongly connected components of a directed graph /// /// Count the strongly connected components of a directed graph /// /// \param g The graph. /// \return The number of components template int countStronglyConnectedComponents(const Graph& graph) { checkConcept(); using namespace _components_bits; typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::EdgeIt EdgeIt; typename Dfs:: template DefProcessedMap >:: Create dfs(graph); std::vector nodes; BackInserterWriteMap processed(nodes); dfs.processedMap(processed); dfs.init(); typedef typename UndirGraph::Node Node; typedef typename UndirGraph::NodeIt NodeIt; typedef typename UndirGraph::Edge Edge; if (NodeIt(graph) == INVALID) return false; Dfs dfs(graph); dfs.init(); typename UndirGraph::template NodeMap red(graph); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } typedef RevGraphAdaptor RGraph; RGraph rgraph(graph); Dfs rdfs(rgraph); int num = 0; rdfs.init(); for (typename std::vector::reverse_iterator it = nodes.rbegin(); it != nodes.rend(); ++it) { if (!rdfs.reached(*it)) { rdfs.addSource(*it); rdfs.start(); ++num; } } return num; } /// \brief Find the strongly connected components of a directed graph /// /// Find the strongly connected components of a directed graph /// /// \param g The graph. /// \retval comp A writable node map. The values will be set from 0 to /// the number of the strongly connected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components template int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) { checkConcept(); checkConcept, IntNodeMap>(); using namespace _components_bits; typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::EdgeIt EdgeIt; typename Dfs:: template DefProcessedMap >:: Create dfs(graph); std::vector nodes; BackInserterWriteMap processed(nodes); dfs.processedMap(processed); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); } } typedef RevGraphAdaptor RGraph; RGraph rgraph(graph); typename Dfs:: template DefProcessedMap >:: Create rdfs(rgraph); int num = 0; FillWriteMap rprocessed(comp, num); rdfs.processedMap(rprocessed); rdfs.init(); for (typename std::vector::reverse_iterator it = nodes.rbegin(); it != nodes.rend(); ++it) { if (!rdfs.reached(*it)) { rdfs.addSource(*it); rdfs.start(); ++num; } } return num; } red[it] = true; while (!dfs.emptyQueue()) { Edge edge = dfs.nextEdge(); Node source = graph.source(edge); Node target = graph.target(edge); if (dfs.reached(target) && red[source] == red[target]) { return false; } else { red[target] = !red[source]; } dfs.processNextEdge(); } } } return true; } } //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.