topology.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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 } //namespace lemon
01465 
01466 #endif //LEMON_TOPOLOGY_H

Generated on Fri Feb 3 18:39:50 2006 for LEMON by  doxygen 1.4.6