00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_DFS_H
00020 #define LEMON_DFS_H
00021
00025
00026 #include <lemon/list_graph.h>
00027 #include <lemon/graph_utils.h>
00028 #include <lemon/invalid.h>
00029 #include <lemon/error.h>
00030 #include <lemon/maps.h>
00031
00032 #include <lemon/concept_check.h>
00033
00034 namespace lemon {
00035
00036
00038
00041 template<class GR>
00042 struct DfsDefaultTraits
00043 {
00045 typedef GR Graph;
00053 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
00055
00059 static PredMap *createPredMap(const GR &G)
00060 {
00061 return new PredMap(G);
00062 }
00063
00065
00069 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
00071
00075 #ifdef DOXYGEN
00076 static ProcessedMap *createProcessedMap(const GR &g)
00077 #else
00078 static ProcessedMap *createProcessedMap(const GR &)
00079 #endif
00080 {
00081 return new ProcessedMap();
00082 }
00084
00088 typedef typename Graph::template NodeMap<bool> ReachedMap;
00090
00094 static ReachedMap *createReachedMap(const GR &G)
00095 {
00096 return new ReachedMap(G);
00097 }
00099
00103 typedef typename Graph::template NodeMap<int> DistMap;
00105
00108 static DistMap *createDistMap(const GR &G)
00109 {
00110 return new DistMap(G);
00111 }
00112 };
00113
00115
00129 #ifdef DOXYGEN
00130 template <typename GR,
00131 typename TR>
00132 #else
00133 template <typename GR=ListGraph,
00134 typename TR=DfsDefaultTraits<GR> >
00135 #endif
00136 class Dfs {
00137 public:
00144 class UninitializedParameter : public lemon::UninitializedParameter {
00145 public:
00146 virtual const char* exceptionName() const {
00147 return "lemon::Dfs::UninitializedParameter";
00148 }
00149 };
00150
00151 typedef TR Traits;
00153 typedef typename TR::Graph Graph;
00155 typedef typename Graph::Node Node;
00157 typedef typename Graph::NodeIt NodeIt;
00159 typedef typename Graph::Edge Edge;
00161 typedef typename Graph::OutEdgeIt OutEdgeIt;
00162
00165 typedef typename TR::PredMap PredMap;
00167 typedef typename TR::ReachedMap ReachedMap;
00169 typedef typename TR::ProcessedMap ProcessedMap;
00171 typedef typename TR::DistMap DistMap;
00172 private:
00174 const Graph *G;
00176 PredMap *_pred;
00178 bool local_pred;
00180 DistMap *_dist;
00182 bool local_dist;
00184 ReachedMap *_reached;
00186 bool local_reached;
00188 ProcessedMap *_processed;
00190 bool local_processed;
00191
00192 std::vector<typename Graph::OutEdgeIt> _stack;
00193 int _stack_head;
00194
00196
00198 void create_maps()
00199 {
00200 if(!_pred) {
00201 local_pred = true;
00202 _pred = Traits::createPredMap(*G);
00203 }
00204 if(!_dist) {
00205 local_dist = true;
00206 _dist = Traits::createDistMap(*G);
00207 }
00208 if(!_reached) {
00209 local_reached = true;
00210 _reached = Traits::createReachedMap(*G);
00211 }
00212 if(!_processed) {
00213 local_processed = true;
00214 _processed = Traits::createProcessedMap(*G);
00215 }
00216 }
00217
00218 protected:
00219
00220 Dfs() {}
00221
00222 public:
00223
00224 typedef Dfs Create;
00225
00227
00229
00230 template <class T>
00231 struct DefPredMapTraits : public Traits {
00232 typedef T PredMap;
00233 static PredMap *createPredMap(const Graph &G)
00234 {
00235 throw UninitializedParameter();
00236 }
00237 };
00239
00242 template <class T>
00243 struct DefPredMap : public Dfs<Graph, DefPredMapTraits<T> > {
00244 typedef Dfs<Graph, DefPredMapTraits<T> > Create;
00245 };
00246
00247
00248 template <class T>
00249 struct DefDistMapTraits : public Traits {
00250 typedef T DistMap;
00251 static DistMap *createDistMap(const Graph &G)
00252 {
00253 throw UninitializedParameter();
00254 }
00255 };
00257
00260 template <class T>
00261 struct DefDistMap {
00262 typedef Dfs<Graph, DefDistMapTraits<T> > Create;
00263 };
00264
00265 template <class T>
00266 struct DefReachedMapTraits : public Traits {
00267 typedef T ReachedMap;
00268 static ReachedMap *createReachedMap(const Graph &G)
00269 {
00270 throw UninitializedParameter();
00271 }
00272 };
00274
00277 template <class T>
00278 struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
00279 typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
00280 };
00281
00282 template <class T>
00283 struct DefProcessedMapTraits : public Traits {
00284 typedef T ProcessedMap;
00285 static ProcessedMap *createProcessedMap(const Graph &G)
00286 {
00287 throw UninitializedParameter();
00288 }
00289 };
00291
00294 template <class T>
00295 struct DefProcessedMap : public Dfs< Graph, DefProcessedMapTraits<T> > {
00296 typedef Dfs< Graph, DefProcessedMapTraits<T> > Create;
00297 };
00298
00299 struct DefGraphProcessedMapTraits : public Traits {
00300 typedef typename Graph::template NodeMap<bool> ProcessedMap;
00301 static ProcessedMap *createProcessedMap(const Graph &G)
00302 {
00303 return new ProcessedMap(G);
00304 }
00305 };
00312 template <class T>
00313 class DefProcessedMapToBeDefaultMap :
00314 public Dfs< Graph, DefGraphProcessedMapTraits> {
00315 typedef Dfs< Graph, DefGraphProcessedMapTraits> Create;
00316 };
00317
00319
00320 public:
00321
00323
00326 Dfs(const Graph& _G) :
00327 G(&_G),
00328 _pred(NULL), local_pred(false),
00329 _dist(NULL), local_dist(false),
00330 _reached(NULL), local_reached(false),
00331 _processed(NULL), local_processed(false)
00332 { }
00333
00335 ~Dfs()
00336 {
00337 if(local_pred) delete _pred;
00338 if(local_dist) delete _dist;
00339 if(local_reached) delete _reached;
00340 if(local_processed) delete _processed;
00341 }
00342
00344
00350 Dfs &predMap(PredMap &m)
00351 {
00352 if(local_pred) {
00353 delete _pred;
00354 local_pred=false;
00355 }
00356 _pred = &m;
00357 return *this;
00358 }
00359
00361
00367 Dfs &distMap(DistMap &m)
00368 {
00369 if(local_dist) {
00370 delete _dist;
00371 local_dist=false;
00372 }
00373 _dist = &m;
00374 return *this;
00375 }
00376
00378
00384 Dfs &reachedMap(ReachedMap &m)
00385 {
00386 if(local_reached) {
00387 delete _reached;
00388 local_reached=false;
00389 }
00390 _reached = &m;
00391 return *this;
00392 }
00393
00395
00401 Dfs &processedMap(ProcessedMap &m)
00402 {
00403 if(local_processed) {
00404 delete _processed;
00405 local_processed=false;
00406 }
00407 _processed = &m;
00408 return *this;
00409 }
00410
00411 public:
00421
00423
00425
00428 void init()
00429 {
00430 create_maps();
00431 _stack.resize(countNodes(*G));
00432 _stack_head=-1;
00433 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
00434 _pred->set(u,INVALID);
00435
00436 _reached->set(u,false);
00437 _processed->set(u,false);
00438 }
00439 }
00440
00442
00447 void addSource(Node s)
00448 {
00449 if(!(*_reached)[s])
00450 {
00451 _reached->set(s,true);
00452 _pred->set(s,INVALID);
00453 OutEdgeIt e(*G,s);
00454 if(e!=INVALID) {
00455 _stack[++_stack_head]=e;
00456 _dist->set(s,_stack_head);
00457 }
00458 else {
00459 _processed->set(s,true);
00460 _dist->set(s,0);
00461 }
00462 }
00463 }
00464
00466
00472 Edge processNextEdge()
00473 {
00474 Node m;
00475 Edge e=_stack[_stack_head];
00476 if(!(*_reached)[m=G->target(e)]) {
00477 _pred->set(m,e);
00478 _reached->set(m,true);
00479 ++_stack_head;
00480 _stack[_stack_head] = OutEdgeIt(*G, m);
00481 _dist->set(m,_stack_head);
00482 }
00483 else {
00484 m=G->source(e);
00485 ++_stack[_stack_head];
00486 }
00487 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
00488 _processed->set(m,true);
00489 --_stack_head;
00490 if(_stack_head>=0) {
00491 m=G->source(_stack[_stack_head]);
00492 ++_stack[_stack_head];
00493 }
00494 }
00495 return e;
00496 }
00498
00503 OutEdgeIt nextEdge()
00504 {
00505 return _stack_head>=0?_stack[_stack_head]:INVALID;
00506 }
00507
00513 bool emptyQueue() { return _stack_head<0; }
00515
00517 int queueSize() { return _stack_head+1; }
00518
00520
00533 void start()
00534 {
00535 while ( !emptyQueue() ) processNextEdge();
00536 }
00537
00539
00552 void start(Node dest)
00553 {
00554 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
00555 processNextEdge();
00556 }
00557
00559
00570 template<class EM>
00571 void start(const EM &em)
00572 {
00573 while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge();
00574 }
00575
00577
00591 void run(Node s) {
00592 init();
00593 addSource(s);
00594 start();
00595 }
00596
00598
00610 int run(Node s,Node t) {
00611 init();
00612 addSource(s);
00613 start(t);
00614 return reached(t)?_stack_head+1:0;
00615 }
00616
00618
00624
00626
00628
00636 template<class P>
00637 bool getPath(P &p,Node t)
00638 {
00639 if(reached(t)) {
00640 p.clear();
00641 typename P::Builder b(p);
00642 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
00643 b.pushFront(predEdge(t));
00644 b.commit();
00645 return true;
00646 }
00647 return false;
00648 }
00649
00651
00656 int dist(Node v) const { return (*_dist)[v]; }
00657
00659
00669 Edge predEdge(Node v) const { return (*_pred)[v];}
00670
00672
00683 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
00684 G->source((*_pred)[v]); }
00685
00687
00691 const DistMap &distMap() const { return *_dist;}
00692
00694
00699 const PredMap &predMap() const { return *_pred;}
00700
00702
00708 bool reached(Node v) { return (*_reached)[v]; }
00709
00711 };
00712
00714
00717 template<class GR>
00718 struct DfsWizardDefaultTraits
00719 {
00721 typedef GR Graph;
00729 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
00731
00735 #ifdef DOXYGEN
00736 static PredMap *createPredMap(const GR &g)
00737 #else
00738 static PredMap *createPredMap(const GR &)
00739 #endif
00740 {
00741 return new PredMap();
00742 }
00743
00745
00749 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
00751
00755 #ifdef DOXYGEN
00756 static ProcessedMap *createProcessedMap(const GR &g)
00757 #else
00758 static ProcessedMap *createProcessedMap(const GR &)
00759 #endif
00760 {
00761 return new ProcessedMap();
00762 }
00764
00768 typedef typename Graph::template NodeMap<bool> ReachedMap;
00770
00774 static ReachedMap *createReachedMap(const GR &G)
00775 {
00776 return new ReachedMap(G);
00777 }
00779
00783 typedef NullMap<typename Graph::Node,int> DistMap;
00785
00788 #ifdef DOXYGEN
00789 static DistMap *createDistMap(const GR &g)
00790 #else
00791 static DistMap *createDistMap(const GR &)
00792 #endif
00793 {
00794 return new DistMap();
00795 }
00796 };
00797
00799
00806 template<class GR>
00807 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
00808 {
00809
00810 typedef DfsWizardDefaultTraits<GR> Base;
00811 protected:
00813 typedef typename Base::Graph::Node Node;
00814
00816 void *_g;
00818 void *_reached;
00820 void *_processed;
00822 void *_pred;
00824 void *_dist;
00826 Node _source;
00827
00828 public:
00830
00833 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
00834 _dist(0), _source(INVALID) {}
00835
00837
00843 DfsWizardBase(const GR &g, Node s=INVALID) :
00844 _g((void *)&g), _reached(0), _processed(0), _pred(0),
00845 _dist(0), _source(s) {}
00846
00847 };
00848
00850
00868 template<class TR>
00869 class DfsWizard : public TR
00870 {
00871 typedef TR Base;
00872
00874 typedef typename TR::Graph Graph;
00875
00876 typedef typename Graph::Node Node;
00877
00878 typedef typename Graph::NodeIt NodeIt;
00879
00880 typedef typename Graph::Edge Edge;
00881
00882 typedef typename Graph::OutEdgeIt OutEdgeIt;
00883
00886 typedef typename TR::ReachedMap ReachedMap;
00889 typedef typename TR::ProcessedMap ProcessedMap;
00892 typedef typename TR::PredMap PredMap;
00894 typedef typename TR::DistMap DistMap;
00895
00896 public:
00898 DfsWizard() : TR() {}
00899
00901
00904 DfsWizard(const Graph &g, Node s=INVALID) :
00905 TR(g,s) {}
00906
00908 DfsWizard(const TR &b) : TR(b) {}
00909
00910 ~DfsWizard() {}
00911
00913
00916 void run()
00917 {
00918 if(Base::_source==INVALID) throw UninitializedParameter();
00919 Dfs<Graph,TR> alg(*(Graph*)Base::_g);
00920 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
00921 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
00922 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
00923 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
00924 alg.run(Base::_source);
00925 }
00926
00928
00931 void run(Node s)
00932 {
00933 Base::_source=s;
00934 run();
00935 }
00936
00937 template<class T>
00938 struct DefPredMapBase : public Base {
00939 typedef T PredMap;
00940 static PredMap *createPredMap(const Graph &) { return 0; };
00941 DefPredMapBase(const TR &b) : TR(b) {}
00942 };
00943
00950 template<class T>
00951 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
00952 {
00953 Base::_pred=(void *)&t;
00954 return DfsWizard<DefPredMapBase<T> >(*this);
00955 }
00956
00957
00958 template<class T>
00959 struct DefReachedMapBase : public Base {
00960 typedef T ReachedMap;
00961 static ReachedMap *createReachedMap(const Graph &) { return 0; };
00962 DefReachedMapBase(const TR &b) : TR(b) {}
00963 };
00964
00971 template<class T>
00972 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
00973 {
00974 Base::_pred=(void *)&t;
00975 return DfsWizard<DefReachedMapBase<T> >(*this);
00976 }
00977
00978
00979 template<class T>
00980 struct DefProcessedMapBase : public Base {
00981 typedef T ProcessedMap;
00982 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
00983 DefProcessedMapBase(const TR &b) : TR(b) {}
00984 };
00985
00992 template<class T>
00993 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
00994 {
00995 Base::_pred=(void *)&t;
00996 return DfsWizard<DefProcessedMapBase<T> >(*this);
00997 }
00998
00999 template<class T>
01000 struct DefDistMapBase : public Base {
01001 typedef T DistMap;
01002 static DistMap *createDistMap(const Graph &) { return 0; };
01003 DefDistMapBase(const TR &b) : TR(b) {}
01004 };
01005
01012 template<class T>
01013 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
01014 {
01015 Base::_dist=(void *)&t;
01016 return DfsWizard<DefDistMapBase<T> >(*this);
01017 }
01018
01020
01023 DfsWizard<TR> &source(Node s)
01024 {
01025 Base::_source=s;
01026 return *this;
01027 }
01028
01029 };
01030
01032
01048 template<class GR>
01049 DfsWizard<DfsWizardBase<GR> >
01050 dfs(const GR &g,typename GR::Node s=INVALID)
01051 {
01052 return DfsWizard<DfsWizardBase<GR> >(g,s);
01053 }
01054
01055 #ifdef DOXYGEN
01060 template <typename _Graph>
01061 struct DfsVisitor {
01062 typedef _Graph Graph;
01063 typedef typename Graph::Edge Edge;
01064 typedef typename Graph::Node Node;
01069 void discover(const Edge& edge) {}
01073 void reach(const Node& node) {}
01077 void backtrack(const Edge& edge) {}
01081 void leave(const Node& node) {}
01087 void examine(const Edge& edge) {}
01091 void start(const Node& node) {}
01095 void stop(const Node& node) {}
01096
01097 };
01098 #else
01099 template <typename _Graph>
01100 struct DfsVisitor {
01101 typedef _Graph Graph;
01102 typedef typename Graph::Edge Edge;
01103 typedef typename Graph::Node Node;
01104 void discover(const Edge&) {}
01105 void reach(const Node&) {}
01106 void backtrack(const Edge&) {}
01107 void leave(const Node&) {}
01108 void examine(const Edge&) {}
01109 void start(const Node&) {}
01110 void stop(const Node&) {}
01111
01112 template <typename _Visitor>
01113 struct Constraints {
01114 void constraints() {
01115 Edge edge;
01116 Node node;
01117 visitor.discover(edge);
01118 visitor.reach(node);
01119 visitor.backtrack(edge);
01120 visitor.leave(node);
01121 visitor.examine(edge);
01122 visitor.start(node);
01123 visitor.stop(edge);
01124 }
01125 _Visitor& visitor;
01126 };
01127 };
01128 #endif
01129
01134 template<class _Graph>
01135 struct DfsVisitDefaultTraits {
01136
01138 typedef _Graph Graph;
01139
01145 typedef typename Graph::template NodeMap<bool> ReachedMap;
01146
01152 static ReachedMap *createReachedMap(const Graph &graph) {
01153 return new ReachedMap(graph);
01154 }
01155
01156 };
01157
01159
01182 #ifdef DOXYGEN
01183 template <typename _Graph, typename _Visitor, typename _Traits>
01184 #else
01185 template <typename _Graph = ListGraph,
01186 typename _Visitor = DfsVisitor<_Graph>,
01187 typename _Traits = DfsDefaultTraits<_Graph> >
01188 #endif
01189 class DfsVisit {
01190 public:
01191
01196 class UninitializedParameter : public lemon::UninitializedParameter {
01197 public:
01198 virtual const char* exceptionName() const {
01199 return "lemon::DfsVisit::UninitializedParameter";
01200 }
01201 };
01202
01203 typedef _Traits Traits;
01204
01205 typedef typename Traits::Graph Graph;
01206
01207 typedef _Visitor Visitor;
01208
01210 typedef typename Traits::ReachedMap ReachedMap;
01211
01212 private:
01213
01214 typedef typename Graph::Node Node;
01215 typedef typename Graph::NodeIt NodeIt;
01216 typedef typename Graph::Edge Edge;
01217 typedef typename Graph::OutEdgeIt OutEdgeIt;
01218
01220 const Graph *_graph;
01222 Visitor *_visitor;
01224 ReachedMap *_reached;
01226 bool local_reached;
01227
01228 std::vector<typename Graph::Edge> _stack;
01229 int _stack_head;
01230
01234 void create_maps() {
01235 if(!_reached) {
01236 local_reached = true;
01237 _reached = Traits::createReachedMap(*_graph);
01238 }
01239 }
01240
01241 protected:
01242
01243 DfsVisit() {}
01244
01245 public:
01246
01247 typedef DfsVisit Create;
01248
01250
01252 template <class T>
01253 struct DefReachedMapTraits : public Traits {
01254 typedef T ReachedMap;
01255 static ReachedMap *createReachedMap(const Graph &graph) {
01256 throw UninitializedParameter();
01257 }
01258 };
01263 template <class T>
01264 struct DefReachedMap : public DfsVisit< Graph, Visitor,
01265 DefReachedMapTraits<T> > {
01266 typedef DfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create;
01267 };
01269
01270 public:
01271
01279 DfsVisit(const Graph& graph, Visitor& visitor)
01280 : _graph(&graph), _visitor(&visitor),
01281 _reached(0), local_reached(false) {}
01282
01286 ~DfsVisit() {
01287 if(local_reached) delete _reached;
01288 }
01289
01297 DfsVisit &reachedMap(ReachedMap &m) {
01298 if(local_reached) {
01299 delete _reached;
01300 local_reached=false;
01301 }
01302 _reached = &m;
01303 return *this;
01304 }
01305
01306 public:
01316
01322 void init() {
01323 create_maps();
01324 _stack.resize(countNodes(*_graph));
01325 _stack_head = -1;
01326 for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
01327 _reached->set(u, false);
01328 }
01329 }
01330
01334 void addSource(Node s) {
01335 if(!(*_reached)[s]) {
01336 _reached->set(s,true);
01337 _visitor->start(s);
01338 _visitor->reach(s);
01339 Edge e;
01340 _graph->firstOut(e, s);
01341 if (e != INVALID) {
01342 _stack[++_stack_head] = e;
01343 } else {
01344 _visitor->leave(s);
01345 }
01346 }
01347 }
01348
01356 Edge processNextEdge() {
01357 Edge e = _stack[_stack_head];
01358 Node m = _graph->target(e);
01359 if(!(*_reached)[m]) {
01360 _visitor->discover(e);
01361 _visitor->reach(m);
01362 _reached->set(m, true);
01363 _graph->firstOut(_stack[++_stack_head], m);
01364 } else {
01365 _visitor->examine(e);
01366 m = _graph->source(e);
01367 _graph->nextOut(_stack[_stack_head]);
01368 }
01369 while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
01370 _visitor->leave(m);
01371 --_stack_head;
01372 if (_stack_head >= 0) {
01373 _visitor->backtrack(_stack[_stack_head]);
01374 m = _graph->source(_stack[_stack_head]);
01375 _graph->nextOut(_stack[_stack_head]);
01376 } else {
01377 _visitor->stop(m);
01378 }
01379 }
01380 return e;
01381 }
01382
01389 Edge nextEdge() {
01390 return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
01391 }
01392
01398 bool emptyQueue() { return _stack_head < 0; }
01399
01403 int queueSize() { return _stack_head + 1; }
01404
01411 void start() {
01412 while ( !emptyQueue() ) processNextEdge();
01413 }
01414
01421 void start(Node dest) {
01422 while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest)
01423 processNextEdge();
01424 }
01425
01438 template <typename EM>
01439 void start(const EM &em) {
01440 while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge();
01441 }
01442
01452 void run(Node s) {
01453 init();
01454 addSource(s);
01455 start();
01456 }
01458
01472 bool reached(Node v) { return (*_reached)[v]; }
01474 };
01475
01476
01477 }
01478
01479 #endif
01480