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