00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_TOPOLOGY_H
00020 #define LEMON_TOPOLOGY_H
00021
00022 #include <lemon/dfs.h>
00023 #include <lemon/bfs.h>
00024 #include <lemon/graph_utils.h>
00025 #include <lemon/graph_adaptor.h>
00026 #include <lemon/maps.h>
00027
00028 #include <lemon/concept/graph.h>
00029 #include <lemon/concept/ugraph.h>
00030 #include <lemon/concept_check.h>
00031
00032 #include <lemon/bin_heap.h>
00033 #include <lemon/linear_heap.h>
00034
00035 #include <stack>
00036 #include <functional>
00037
00043
00044 namespace lemon {
00045
00054 template <typename UGraph>
00055 bool connected(const UGraph& graph) {
00056 checkConcept<concept::UGraph, UGraph>();
00057 typedef typename UGraph::NodeIt NodeIt;
00058 if (NodeIt(graph) == INVALID) return true;
00059 Dfs<UGraph> dfs(graph);
00060 dfs.run(NodeIt(graph));
00061 for (NodeIt it(graph); it != INVALID; ++it) {
00062 if (!dfs.reached(it)) {
00063 return false;
00064 }
00065 }
00066 return true;
00067 }
00068
00079 template <typename UGraph>
00080 int countConnectedComponents(const UGraph &graph) {
00081 checkConcept<concept::UGraph, UGraph>();
00082 typedef typename UGraph::Node Node;
00083 typedef typename UGraph::Edge Edge;
00084
00085 typedef NullMap<Node, Edge> PredMap;
00086 typedef NullMap<Node, int> DistMap;
00087
00088 int compNum = 0;
00089 typename Bfs<UGraph>::
00090 template DefPredMap<PredMap>::
00091 template DefDistMap<DistMap>::
00092 Create bfs(graph);
00093
00094 PredMap predMap;
00095 bfs.predMap(predMap);
00096
00097 DistMap distMap;
00098 bfs.distMap(distMap);
00099
00100 bfs.init();
00101 for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
00102 if (!bfs.reached(n)) {
00103 bfs.addSource(n);
00104 bfs.start();
00105 ++compNum;
00106 }
00107 }
00108 return compNum;
00109 }
00110
00127 template <class UGraph, class NodeMap>
00128 int connectedComponents(const UGraph &graph, NodeMap &compMap) {
00129 checkConcept<concept::UGraph, UGraph>();
00130 typedef typename UGraph::Node Node;
00131 typedef typename UGraph::Edge Edge;
00132 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
00133
00134 typedef NullMap<Node, Edge> PredMap;
00135 typedef NullMap<Node, int> DistMap;
00136
00137 int compNum = 0;
00138 typename Bfs<UGraph>::
00139 template DefPredMap<PredMap>::
00140 template DefDistMap<DistMap>::
00141 Create bfs(graph);
00142
00143 PredMap predMap;
00144 bfs.predMap(predMap);
00145
00146 DistMap distMap;
00147 bfs.distMap(distMap);
00148
00149 bfs.init();
00150 for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
00151 if(!bfs.reached(n)) {
00152 bfs.addSource(n);
00153 while (!bfs.emptyQueue()) {
00154 compMap.set(bfs.nextNode(), compNum);
00155 bfs.processNextNode();
00156 }
00157 ++compNum;
00158 }
00159 }
00160 return compNum;
00161 }
00162
00163 namespace _topology_bits {
00164
00165 template <typename Graph, typename Iterator >
00166 struct LeaveOrderVisitor : public DfsVisitor<Graph> {
00167 public:
00168 typedef typename Graph::Node Node;
00169 LeaveOrderVisitor(Iterator it) : _it(it) {}
00170
00171 void leave(const Node& node) {
00172 *(_it++) = node;
00173 }
00174
00175 private:
00176 Iterator _it;
00177 };
00178
00179 template <typename Graph, typename Map>
00180 struct FillMapVisitor : public DfsVisitor<Graph> {
00181 public:
00182 typedef typename Graph::Node Node;
00183 typedef typename Map::Value Value;
00184
00185 FillMapVisitor(Map& map, Value& value)
00186 : _map(map), _value(value) {}
00187
00188 void reach(const Node& node) {
00189 _map.set(node, _value);
00190 }
00191 private:
00192 Map& _map;
00193 Value& _value;
00194 };
00195
00196 template <typename Graph, typename EdgeMap>
00197 struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
00198 public:
00199 typedef typename Graph::Node Node;
00200 typedef typename Graph::Edge Edge;
00201
00202 StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap,
00203 int& cutNum)
00204 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
00205 _compMap(graph), _num(0) {
00206 }
00207
00208 void stop(const Node&) {
00209 ++_num;
00210 }
00211
00212 void reach(const Node& node) {
00213 _compMap.set(node, _num);
00214 }
00215
00216 void examine(const Edge& edge) {
00217 if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) {
00218 _cutMap.set(edge, true);
00219 ++_cutNum;
00220 }
00221 }
00222 private:
00223 const Graph& _graph;
00224 EdgeMap& _cutMap;
00225 int& _cutNum;
00226
00227 typename Graph::template NodeMap<int> _compMap;
00228 int _num;
00229 };
00230
00231 }
00232
00233
00245 template <typename Graph>
00246 bool stronglyConnected(const Graph& graph) {
00247 checkConcept<concept::StaticGraph, Graph>();
00248 if (NodeIt(graph) == INVALID) return true;
00249
00250 typedef typename Graph::Node Node;
00251 typedef typename Graph::NodeIt NodeIt;
00252
00253 using namespace _topology_bits;
00254
00255 typedef DfsVisitor<Graph> Visitor;
00256 Visitor visitor;
00257
00258 DfsVisit<Graph, Visitor> dfs(graph, visitor);
00259 dfs.init();
00260 dfs.addSource(NodeIt(graph));
00261 dfs.start();
00262
00263 for (NodeIt it(graph); it != INVALID; ++it) {
00264 if (!dfs.reached(it)) {
00265 return false;
00266 }
00267 }
00268
00269 typedef RevGraphAdaptor<const Graph> RGraph;
00270 RGraph rgraph(graph);
00271
00272 typedef DfsVisitor<Graph> RVisitor;
00273 RVisitor rvisitor;
00274
00275 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
00276 rdfs.init();
00277 rdfs.addSource(NodeIt(graph));
00278 rdfs.start();
00279
00280 for (NodeIt it(graph); it != INVALID; ++it) {
00281 if (!rdfs.reached(it)) {
00282 return false;
00283 }
00284 }
00285
00286 return true;
00287 }
00288
00302 template <typename Graph>
00303 int countStronglyConnectedComponents(const Graph& graph) {
00304 checkConcept<concept::StaticGraph, Graph>();
00305
00306 using namespace _topology_bits;
00307
00308 typedef typename Graph::Node Node;
00309 typedef typename Graph::Edge Edge;
00310 typedef typename Graph::NodeIt NodeIt;
00311 typedef typename Graph::EdgeIt EdgeIt;
00312
00313 typedef std::vector<Node> Container;
00314 typedef typename Container::iterator Iterator;
00315
00316 Container nodes(countNodes(graph));
00317 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
00318 Visitor visitor(nodes.begin());
00319
00320 DfsVisit<Graph, Visitor> dfs(graph, visitor);
00321 dfs.init();
00322 for (NodeIt it(graph); it != INVALID; ++it) {
00323 if (!dfs.reached(it)) {
00324 dfs.addSource(it);
00325 dfs.start();
00326 }
00327 }
00328
00329 typedef typename Container::reverse_iterator RIterator;
00330 typedef RevGraphAdaptor<const Graph> RGraph;
00331
00332 RGraph rgraph(graph);
00333
00334 typedef DfsVisitor<Graph> RVisitor;
00335 RVisitor rvisitor;
00336
00337 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
00338
00339 int compNum = 0;
00340
00341 rdfs.init();
00342 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
00343 if (!rdfs.reached(*it)) {
00344 rdfs.addSource(*it);
00345 rdfs.start();
00346 ++compNum;
00347 }
00348 }
00349 return compNum;
00350 }
00351
00371 template <typename Graph, typename NodeMap>
00372 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
00373 checkConcept<concept::StaticGraph, Graph>();
00374 typedef typename Graph::Node Node;
00375 typedef typename Graph::NodeIt NodeIt;
00376 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
00377
00378 using namespace _topology_bits;
00379
00380 typedef std::vector<Node> Container;
00381 typedef typename Container::iterator Iterator;
00382
00383 Container nodes(countNodes(graph));
00384 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
00385 Visitor visitor(nodes.begin());
00386
00387 DfsVisit<Graph, Visitor> dfs(graph, visitor);
00388 dfs.init();
00389 for (NodeIt it(graph); it != INVALID; ++it) {
00390 if (!dfs.reached(it)) {
00391 dfs.addSource(it);
00392 dfs.start();
00393 }
00394 }
00395
00396 typedef typename Container::reverse_iterator RIterator;
00397 typedef RevGraphAdaptor<const Graph> RGraph;
00398
00399 RGraph rgraph(graph);
00400
00401 int compNum = 0;
00402
00403 typedef FillMapVisitor<RGraph, NodeMap> RVisitor;
00404 RVisitor rvisitor(compMap, compNum);
00405
00406 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
00407
00408 rdfs.init();
00409 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
00410 if (!rdfs.reached(*it)) {
00411 rdfs.addSource(*it);
00412 rdfs.start();
00413 ++compNum;
00414 }
00415 }
00416 return compNum;
00417 }
00418
00434 template <typename Graph, typename EdgeMap>
00435 int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
00436 checkConcept<concept::StaticGraph, Graph>();
00437 typedef typename Graph::Node Node;
00438 typedef typename Graph::Edge Edge;
00439 typedef typename Graph::NodeIt NodeIt;
00440 checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>();
00441
00442 using namespace _topology_bits;
00443
00444 typedef std::vector<Node> Container;
00445 typedef typename Container::iterator Iterator;
00446
00447 Container nodes(countNodes(graph));
00448 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
00449 Visitor visitor(nodes.begin());
00450
00451 DfsVisit<Graph, Visitor> dfs(graph, visitor);
00452 dfs.init();
00453 for (NodeIt it(graph); it != INVALID; ++it) {
00454 if (!dfs.reached(it)) {
00455 dfs.addSource(it);
00456 dfs.start();
00457 }
00458 }
00459
00460 typedef typename Container::reverse_iterator RIterator;
00461 typedef RevGraphAdaptor<const Graph> RGraph;
00462
00463 RGraph rgraph(graph);
00464
00465 int cutNum = 0;
00466
00467 typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;
00468 RVisitor rvisitor(rgraph, cutMap, cutNum);
00469
00470 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
00471
00472 rdfs.init();
00473 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
00474 if (!rdfs.reached(*it)) {
00475 rdfs.addSource(*it);
00476 rdfs.start();
00477 }
00478 }
00479 return cutNum;
00480 }
00481
00482 namespace _topology_bits {
00483
00484 template <typename Graph>
00485 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
00486 public:
00487 typedef typename Graph::Node Node;
00488 typedef typename Graph::Edge Edge;
00489 typedef typename Graph::UEdge UEdge;
00490
00491 CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum)
00492 : _graph(graph), _compNum(compNum),
00493 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
00494
00495 void start(const Node& node) {
00496 _predMap.set(node, INVALID);
00497 }
00498
00499 void reach(const Node& node) {
00500 _numMap.set(node, _num);
00501 _retMap.set(node, _num);
00502 ++_num;
00503 }
00504
00505 void discover(const Edge& edge) {
00506 _predMap.set(_graph.target(edge), _graph.source(edge));
00507 }
00508
00509 void examine(const Edge& edge) {
00510 if (_graph.source(edge) == _graph.target(edge) &&
00511 _graph.direction(edge)) {
00512 ++_compNum;
00513 return;
00514 }
00515 if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
00516 return;
00517 }
00518 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
00519 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
00520 }
00521 }
00522
00523 void backtrack(const Edge& edge) {
00524 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
00525 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
00526 }
00527 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
00528 ++_compNum;
00529 }
00530 }
00531
00532 private:
00533 const Graph& _graph;
00534 int& _compNum;
00535
00536 typename Graph::template NodeMap<int> _numMap;
00537 typename Graph::template NodeMap<int> _retMap;
00538 typename Graph::template NodeMap<Node> _predMap;
00539 int _num;
00540 };
00541
00542 template <typename Graph, typename EdgeMap>
00543 class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
00544 public:
00545 typedef typename Graph::Node Node;
00546 typedef typename Graph::Edge Edge;
00547 typedef typename Graph::UEdge UEdge;
00548
00549 BiNodeConnectedComponentsVisitor(const Graph& graph,
00550 EdgeMap& compMap, int &compNum)
00551 : _graph(graph), _compMap(compMap), _compNum(compNum),
00552 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
00553
00554 void start(const Node& node) {
00555 _predMap.set(node, INVALID);
00556 }
00557
00558 void reach(const Node& node) {
00559 _numMap.set(node, _num);
00560 _retMap.set(node, _num);
00561 ++_num;
00562 }
00563
00564 void discover(const Edge& edge) {
00565 Node target = _graph.target(edge);
00566 _predMap.set(target, edge);
00567 _edgeStack.push(edge);
00568 }
00569
00570 void examine(const Edge& edge) {
00571 Node source = _graph.source(edge);
00572 Node target = _graph.target(edge);
00573 if (source == target && _graph.direction(edge)) {
00574 _compMap.set(edge, _compNum);
00575 ++_compNum;
00576 return;
00577 }
00578 if (_numMap[target] < _numMap[source]) {
00579 if (_predMap[source] != _graph.oppositeEdge(edge)) {
00580 _edgeStack.push(edge);
00581 }
00582 }
00583 if (_predMap[source] != INVALID &&
00584 target == _graph.source(_predMap[source])) {
00585 return;
00586 }
00587 if (_retMap[source] > _numMap[target]) {
00588 _retMap.set(source, _numMap[target]);
00589 }
00590 }
00591
00592 void backtrack(const Edge& edge) {
00593 Node source = _graph.source(edge);
00594 Node target = _graph.target(edge);
00595 if (_retMap[source] > _retMap[target]) {
00596 _retMap.set(source, _retMap[target]);
00597 }
00598 if (_numMap[source] <= _retMap[target]) {
00599 while (_edgeStack.top() != edge) {
00600 _compMap.set(_edgeStack.top(), _compNum);
00601 _edgeStack.pop();
00602 }
00603 _compMap.set(edge, _compNum);
00604 _edgeStack.pop();
00605 ++_compNum;
00606 }
00607 }
00608
00609 private:
00610 const Graph& _graph;
00611 EdgeMap& _compMap;
00612 int& _compNum;
00613
00614 typename Graph::template NodeMap<int> _numMap;
00615 typename Graph::template NodeMap<int> _retMap;
00616 typename Graph::template NodeMap<Edge> _predMap;
00617 std::stack<UEdge> _edgeStack;
00618 int _num;
00619 };
00620
00621
00622 template <typename Graph, typename NodeMap>
00623 class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
00624 public:
00625 typedef typename Graph::Node Node;
00626 typedef typename Graph::Edge Edge;
00627 typedef typename Graph::UEdge UEdge;
00628
00629 BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
00630 int& cutNum)
00631 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
00632 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
00633
00634 void start(const Node& node) {
00635 _predMap.set(node, INVALID);
00636 rootCut = false;
00637 }
00638
00639 void reach(const Node& node) {
00640 _numMap.set(node, _num);
00641 _retMap.set(node, _num);
00642 ++_num;
00643 }
00644
00645 void discover(const Edge& edge) {
00646 _predMap.set(_graph.target(edge), _graph.source(edge));
00647 }
00648
00649 void examine(const Edge& edge) {
00650 if (_graph.source(edge) == _graph.target(edge) &&
00651 _graph.direction(edge)) {
00652 if (!_cutMap[_graph.source(edge)]) {
00653 _cutMap.set(_graph.source(edge), true);
00654 ++_cutNum;
00655 }
00656 return;
00657 }
00658 if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
00659 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
00660 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
00661 }
00662 }
00663
00664 void backtrack(const Edge& edge) {
00665 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
00666 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
00667 }
00668 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
00669 if (_predMap[_graph.source(edge)] != INVALID) {
00670 if (!_cutMap[_graph.source(edge)]) {
00671 _cutMap.set(_graph.source(edge), true);
00672 ++_cutNum;
00673 }
00674 } else if (rootCut) {
00675 if (!_cutMap[_graph.source(edge)]) {
00676 _cutMap.set(_graph.source(edge), true);
00677 ++_cutNum;
00678 }
00679 } else {
00680 rootCut = true;
00681 }
00682 }
00683 }
00684
00685 private:
00686 const Graph& _graph;
00687 NodeMap& _cutMap;
00688 int& _cutNum;
00689
00690 typename Graph::template NodeMap<int> _numMap;
00691 typename Graph::template NodeMap<int> _retMap;
00692 typename Graph::template NodeMap<Node> _predMap;
00693 std::stack<UEdge> _edgeStack;
00694 int _num;
00695 bool rootCut;
00696 };
00697
00698 }
00699
00700 template <typename UGraph>
00701 int countBiNodeConnectedComponents(const UGraph& graph);
00702
00714 template <typename UGraph>
00715 bool biNodeConnected(const UGraph& graph) {
00716 return countBiNodeConnectedComponents(graph) == 1;
00717 }
00718
00730 template <typename UGraph>
00731 int countBiNodeConnectedComponents(const UGraph& graph) {
00732 checkConcept<concept::UGraph, UGraph>();
00733 typedef typename UGraph::NodeIt NodeIt;
00734
00735 using namespace _topology_bits;
00736
00737 typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor;
00738
00739 int compNum = 0;
00740 Visitor visitor(graph, compNum);
00741
00742 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
00743 dfs.init();
00744
00745 for (NodeIt it(graph); it != INVALID; ++it) {
00746 if (!dfs.reached(it)) {
00747 dfs.addSource(it);
00748 dfs.start();
00749 }
00750 }
00751 return compNum;
00752 }
00753
00773 template <typename UGraph, typename UEdgeMap>
00774 int biNodeConnectedComponents(const UGraph& graph,
00775 UEdgeMap& compMap) {
00776 checkConcept<concept::UGraph, UGraph>();
00777 typedef typename UGraph::NodeIt NodeIt;
00778 typedef typename UGraph::UEdge UEdge;
00779 checkConcept<concept::WriteMap<UEdge, int>, UEdgeMap>();
00780
00781 using namespace _topology_bits;
00782
00783 typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor;
00784
00785 int compNum = 0;
00786 Visitor visitor(graph, compMap, compNum);
00787
00788 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
00789 dfs.init();
00790
00791 for (NodeIt it(graph); it != INVALID; ++it) {
00792 if (!dfs.reached(it)) {
00793 dfs.addSource(it);
00794 dfs.start();
00795 }
00796 }
00797 return compNum;
00798 }
00799
00814 template <typename UGraph, typename NodeMap>
00815 int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) {
00816 checkConcept<concept::UGraph, UGraph>();
00817 typedef typename UGraph::Node Node;
00818 typedef typename UGraph::NodeIt NodeIt;
00819 checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
00820
00821 using namespace _topology_bits;
00822
00823 typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor;
00824
00825 int cutNum = 0;
00826 Visitor visitor(graph, cutMap, cutNum);
00827
00828 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
00829 dfs.init();
00830
00831 for (NodeIt it(graph); it != INVALID; ++it) {
00832 if (!dfs.reached(it)) {
00833 dfs.addSource(it);
00834 dfs.start();
00835 }
00836 }
00837 return cutNum;
00838 }
00839
00840 namespace _topology_bits {
00841
00842 template <typename Graph>
00843 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
00844 public:
00845 typedef typename Graph::Node Node;
00846 typedef typename Graph::Edge Edge;
00847 typedef typename Graph::UEdge UEdge;
00848
00849 CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum)
00850 : _graph(graph), _compNum(compNum),
00851 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
00852
00853 void start(const Node& node) {
00854 _predMap.set(node, INVALID);
00855 }
00856
00857 void reach(const Node& node) {
00858 _numMap.set(node, _num);
00859 _retMap.set(node, _num);
00860 ++_num;
00861 }
00862
00863 void leave(const Node& node) {
00864 if (_numMap[node] <= _retMap[node]) {
00865 ++_compNum;
00866 }
00867 }
00868
00869 void discover(const Edge& edge) {
00870 _predMap.set(_graph.target(edge), edge);
00871 }
00872
00873 void examine(const Edge& edge) {
00874 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
00875 return;
00876 }
00877 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
00878 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
00879 }
00880 }
00881
00882 void backtrack(const Edge& edge) {
00883 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
00884 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
00885 }
00886 }
00887
00888 private:
00889 const Graph& _graph;
00890 int& _compNum;
00891
00892 typename Graph::template NodeMap<int> _numMap;
00893 typename Graph::template NodeMap<int> _retMap;
00894 typename Graph::template NodeMap<Edge> _predMap;
00895 int _num;
00896 };
00897
00898 template <typename Graph, typename NodeMap>
00899 class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
00900 public:
00901 typedef typename Graph::Node Node;
00902 typedef typename Graph::Edge Edge;
00903 typedef typename Graph::UEdge UEdge;
00904
00905 BiEdgeConnectedComponentsVisitor(const Graph& graph,
00906 NodeMap& compMap, int &compNum)
00907 : _graph(graph), _compMap(compMap), _compNum(compNum),
00908 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
00909
00910 void start(const Node& node) {
00911 _predMap.set(node, INVALID);
00912 }
00913
00914 void reach(const Node& node) {
00915 _numMap.set(node, _num);
00916 _retMap.set(node, _num);
00917 _nodeStack.push(node);
00918 ++_num;
00919 }
00920
00921 void leave(const Node& node) {
00922 if (_numMap[node] <= _retMap[node]) {
00923 while (_nodeStack.top() != node) {
00924 _compMap.set(_nodeStack.top(), _compNum);
00925 _nodeStack.pop();
00926 }
00927 _compMap.set(node, _compNum);
00928 _nodeStack.pop();
00929 ++_compNum;
00930 }
00931 }
00932
00933 void discover(const Edge& edge) {
00934 _predMap.set(_graph.target(edge), edge);
00935 }
00936
00937 void examine(const Edge& edge) {
00938 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
00939 return;
00940 }
00941 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
00942 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
00943 }
00944 }
00945
00946 void backtrack(const Edge& edge) {
00947 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
00948 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
00949 }
00950 }
00951
00952 private:
00953 const Graph& _graph;
00954 NodeMap& _compMap;
00955 int& _compNum;
00956
00957 typename Graph::template NodeMap<int> _numMap;
00958 typename Graph::template NodeMap<int> _retMap;
00959 typename Graph::template NodeMap<Edge> _predMap;
00960 std::stack<Node> _nodeStack;
00961 int _num;
00962 };
00963
00964
00965 template <typename Graph, typename EdgeMap>
00966 class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
00967 public:
00968 typedef typename Graph::Node Node;
00969 typedef typename Graph::Edge Edge;
00970 typedef typename Graph::UEdge UEdge;
00971
00972 BiEdgeConnectedCutEdgesVisitor(const Graph& graph,
00973 EdgeMap& cutMap, int &cutNum)
00974 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
00975 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
00976
00977 void start(const Node& node) {
00978 _predMap[node] = INVALID;
00979 }
00980
00981 void reach(const Node& node) {
00982 _numMap.set(node, _num);
00983 _retMap.set(node, _num);
00984 ++_num;
00985 }
00986
00987 void leave(const Node& node) {
00988 if (_numMap[node] <= _retMap[node]) {
00989 if (_predMap[node] != INVALID) {
00990 _cutMap.set(_predMap[node], true);
00991 ++_cutNum;
00992 }
00993 }
00994 }
00995
00996 void discover(const Edge& edge) {
00997 _predMap.set(_graph.target(edge), edge);
00998 }
00999
01000 void examine(const Edge& edge) {
01001 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
01002 return;
01003 }
01004 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
01005 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
01006 }
01007 }
01008
01009 void backtrack(const Edge& edge) {
01010 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
01011 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
01012 }
01013 }
01014
01015 private:
01016 const Graph& _graph;
01017 EdgeMap& _cutMap;
01018 int& _cutNum;
01019
01020 typename Graph::template NodeMap<int> _numMap;
01021 typename Graph::template NodeMap<int> _retMap;
01022 typename Graph::template NodeMap<Edge> _predMap;
01023 int _num;
01024 };
01025 }
01026
01027 template <typename UGraph>
01028 int countbiEdgeConnectedComponents(const UGraph& graph);
01029
01041 template <typename UGraph>
01042 bool biEdgeConnected(const UGraph& graph) {
01043 return countBiEdgeConnectedComponents(graph) == 1;
01044 }
01045
01057 template <typename UGraph>
01058 int countBiEdgeConnectedComponents(const UGraph& graph) {
01059 checkConcept<concept::UGraph, UGraph>();
01060 typedef typename UGraph::NodeIt NodeIt;
01061
01062 using namespace _topology_bits;
01063
01064 typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor;
01065
01066 int compNum = 0;
01067 Visitor visitor(graph, compNum);
01068
01069 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
01070 dfs.init();
01071
01072 for (NodeIt it(graph); it != INVALID; ++it) {
01073 if (!dfs.reached(it)) {
01074 dfs.addSource(it);
01075 dfs.start();
01076 }
01077 }
01078 return compNum;
01079 }
01080
01100 template <typename UGraph, typename NodeMap>
01101 int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) {
01102 checkConcept<concept::UGraph, UGraph>();
01103 typedef typename UGraph::NodeIt NodeIt;
01104 typedef typename UGraph::Node Node;
01105 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
01106
01107 using namespace _topology_bits;
01108
01109 typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor;
01110
01111 int compNum = 0;
01112 Visitor visitor(graph, compMap, compNum);
01113
01114 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
01115 dfs.init();
01116
01117 for (NodeIt it(graph); it != INVALID; ++it) {
01118 if (!dfs.reached(it)) {
01119 dfs.addSource(it);
01120 dfs.start();
01121 }
01122 }
01123 return compNum;
01124 }
01125
01141 template <typename UGraph, typename UEdgeMap>
01142 int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) {
01143 checkConcept<concept::UGraph, UGraph>();
01144 typedef typename UGraph::NodeIt NodeIt;
01145 typedef typename UGraph::UEdge UEdge;
01146 checkConcept<concept::WriteMap<UEdge, bool>, UEdgeMap>();
01147
01148 using namespace _topology_bits;
01149
01150 typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor;
01151
01152 int cutNum = 0;
01153 Visitor visitor(graph, cutMap, cutNum);
01154
01155 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
01156 dfs.init();
01157
01158 for (NodeIt it(graph); it != INVALID; ++it) {
01159 if (!dfs.reached(it)) {
01160 dfs.addSource(it);
01161 dfs.start();
01162 }
01163 }
01164 return cutNum;
01165 }
01166
01167
01168 namespace _topology_bits {
01169
01170 template <typename Graph, typename IntNodeMap>
01171 class TopologicalSortVisitor : public DfsVisitor<Graph> {
01172 public:
01173 typedef typename Graph::Node Node;
01174 typedef typename Graph::Edge edge;
01175
01176 TopologicalSortVisitor(IntNodeMap& order, int num)
01177 : _order(order), _num(num) {}
01178
01179 void leave(const Node& node) {
01180 _order.set(node, --_num);
01181 }
01182
01183 private:
01184 IntNodeMap& _order;
01185 int _num;
01186 };
01187
01188 }
01189
01203 template <typename Graph, typename NodeMap>
01204 void topologicalSort(const Graph& graph, NodeMap& order) {
01205 using namespace _topology_bits;
01206
01207 checkConcept<concept::StaticGraph, Graph>();
01208 checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
01209
01210 typedef typename Graph::Node Node;
01211 typedef typename Graph::NodeIt NodeIt;
01212 typedef typename Graph::Edge Edge;
01213
01214 TopologicalSortVisitor<Graph, NodeMap>
01215 visitor(order, countNodes(graph));
01216
01217 DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
01218 dfs(graph, visitor);
01219
01220 dfs.init();
01221 for (NodeIt it(graph); it != INVALID; ++it) {
01222 if (!dfs.reached(it)) {
01223 dfs.addSource(it);
01224 dfs.start();
01225 }
01226 }
01227 }
01228
01245 template <typename Graph, typename NodeMap>
01246 bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
01247 using namespace _topology_bits;
01248
01249 checkConcept<concept::StaticGraph, Graph>();
01250 checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
01251
01252 typedef typename Graph::Node Node;
01253 typedef typename Graph::NodeIt NodeIt;
01254 typedef typename Graph::Edge Edge;
01255
01256 order = constMap<Node, int, -1>();
01257
01258 TopologicalSortVisitor<Graph, NodeMap>
01259 visitor(order, countNodes(graph));
01260
01261 DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
01262 dfs(graph, visitor);
01263
01264 dfs.init();
01265 for (NodeIt it(graph); it != INVALID; ++it) {
01266 if (!dfs.reached(it)) {
01267 dfs.addSource(it);
01268 while (!dfs.emptyQueue()) {
01269 Edge edge = dfs.nextEdge();
01270 Node target = graph.target(edge);
01271 if (dfs.reached(target) && order[target] == -1) {
01272 return false;
01273 }
01274 dfs.processNextEdge();
01275 }
01276 }
01277 }
01278 return true;
01279 }
01280
01289 template <typename Graph>
01290 bool dag(const Graph& graph) {
01291
01292 checkConcept<concept::StaticGraph, Graph>();
01293
01294 typedef typename Graph::Node Node;
01295 typedef typename Graph::NodeIt NodeIt;
01296 typedef typename Graph::Edge Edge;
01297
01298 typedef typename Graph::template NodeMap<bool> ProcessedMap;
01299
01300 typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
01301 Create dfs(graph);
01302
01303 ProcessedMap processed(graph);
01304 dfs.processedMap(processed);
01305
01306 dfs.init();
01307 for (NodeIt it(graph); it != INVALID; ++it) {
01308 if (!dfs.reached(it)) {
01309 dfs.addSource(it);
01310 while (!dfs.emptyQueue()) {
01311 Edge edge = dfs.nextEdge();
01312 Node target = graph.target(edge);
01313 if (dfs.reached(target) && !processed[target]) {
01314 return false;
01315 }
01316 dfs.processNextEdge();
01317 }
01318 }
01319 }
01320 return true;
01321 }
01322
01331 template <typename UGraph>
01332 bool acyclic(const UGraph& graph) {
01333 checkConcept<concept::UGraph, UGraph>();
01334 typedef typename UGraph::Node Node;
01335 typedef typename UGraph::NodeIt NodeIt;
01336 typedef typename UGraph::Edge Edge;
01337 Dfs<UGraph> dfs(graph);
01338 dfs.init();
01339 for (NodeIt it(graph); it != INVALID; ++it) {
01340 if (!dfs.reached(it)) {
01341 dfs.addSource(it);
01342 while (!dfs.emptyQueue()) {
01343 Edge edge = dfs.nextEdge();
01344 Node source = graph.source(edge);
01345 Node target = graph.target(edge);
01346 if (dfs.reached(target) &&
01347 dfs.predEdge(source) != graph.oppositeEdge(edge)) {
01348 return false;
01349 }
01350 dfs.processNextEdge();
01351 }
01352 }
01353 }
01354 return true;
01355 }
01356
01364 template <typename UGraph>
01365 bool tree(const UGraph& graph) {
01366 checkConcept<concept::UGraph, UGraph>();
01367 typedef typename UGraph::Node Node;
01368 typedef typename UGraph::NodeIt NodeIt;
01369 typedef typename UGraph::Edge Edge;
01370 Dfs<UGraph> dfs(graph);
01371 dfs.init();
01372 dfs.addSource(NodeIt(graph));
01373 while (!dfs.emptyQueue()) {
01374 Edge edge = dfs.nextEdge();
01375 Node source = graph.source(edge);
01376 Node target = graph.target(edge);
01377 if (dfs.reached(target) &&
01378 dfs.predEdge(source) != graph.oppositeEdge(edge)) {
01379 return false;
01380 }
01381 dfs.processNextEdge();
01382 }
01383 for (NodeIt it(graph); it != INVALID; ++it) {
01384 if (!dfs.reached(it)) {
01385 return false;
01386 }
01387 }
01388 return true;
01389 }
01390
01402 template<typename UGraph>
01403 inline bool bipartite(const UGraph &graph){
01404 checkConcept<concept::UGraph, UGraph>();
01405
01406 typedef typename UGraph::NodeIt NodeIt;
01407 typedef typename UGraph::EdgeIt EdgeIt;
01408
01409 Bfs<UGraph> bfs(graph);
01410 bfs.init();
01411 for(NodeIt i(graph);i!=INVALID;++i){
01412 if(!bfs.reached(i)){
01413 bfs.run(i);
01414 }
01415 }
01416 for(EdgeIt i(graph);i!=INVALID;++i){
01417 if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
01418 }
01419 return true;
01420 };
01421
01439 template<typename UGraph, typename NodeMap>
01440 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
01441 checkConcept<concept::UGraph, UGraph>();
01442
01443 typedef typename UGraph::Node Node;
01444 typedef typename UGraph::NodeIt NodeIt;
01445 typedef typename UGraph::EdgeIt EdgeIt;
01446
01447 Bfs<UGraph> bfs(graph);
01448 bfs.init();
01449 for(NodeIt i(graph);i!=INVALID;++i){
01450 if(!bfs.reached(i)){
01451 bfs.addSource(i);
01452 for(Node j=bfs.processNextNode();!bfs.emptyQueue();
01453 j=bfs.processNextNode()){
01454 partMap.set(j,bfs.dist(j)%2==0);
01455 }
01456 }
01457 }
01458 for(EdgeIt i(graph);i!=INVALID;++i){
01459 if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
01460 }
01461 return true;
01462 };
01463
01464 }
01465
01466 #endif //LEMON_TOPOLOGY_H