00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_BFS_H
00020 #define LEMON_BFS_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 namespace lemon {
00033
00034
00035
00037
00040 template<class GR>
00041 struct BfsDefaultTraits
00042 {
00044 typedef GR Graph;
00052 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
00054
00058 static PredMap *createPredMap(const GR &G)
00059 {
00060 return new PredMap(G);
00061 }
00063
00067 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
00069
00073 #ifdef DOXYGEN
00074 static ProcessedMap *createProcessedMap(const GR &g)
00075 #else
00076 static ProcessedMap *createProcessedMap(const GR &)
00077 #endif
00078 {
00079 return new ProcessedMap();
00080 }
00082
00086 typedef typename Graph::template NodeMap<bool> ReachedMap;
00088
00092 static ReachedMap *createReachedMap(const GR &G)
00093 {
00094 return new ReachedMap(G);
00095 }
00097
00101 typedef typename Graph::template NodeMap<int> DistMap;
00103
00106 static DistMap *createDistMap(const GR &G)
00107 {
00108 return new DistMap(G);
00109 }
00110 };
00111
00113
00127
00128 #ifdef DOXYGEN
00129 template <typename GR,
00130 typename TR>
00131 #else
00132 template <typename GR=ListGraph,
00133 typename TR=BfsDefaultTraits<GR> >
00134 #endif
00135 class Bfs {
00136 public:
00143 class UninitializedParameter : public lemon::UninitializedParameter {
00144 public:
00145 virtual const char* exceptionName() const {
00146 return "lemon::Bfs::UninitializedParameter";
00147 }
00148 };
00149
00150 typedef TR Traits;
00152 typedef typename TR::Graph Graph;
00154 typedef typename Graph::Node Node;
00156 typedef typename Graph::NodeIt NodeIt;
00158 typedef typename Graph::Edge Edge;
00160 typedef typename Graph::OutEdgeIt OutEdgeIt;
00161
00164 typedef typename TR::PredMap PredMap;
00166 typedef typename TR::ReachedMap ReachedMap;
00168 typedef typename TR::ProcessedMap ProcessedMap;
00170 typedef typename TR::DistMap DistMap;
00171 private:
00173 const Graph *G;
00175 PredMap *_pred;
00177 bool local_pred;
00179 DistMap *_dist;
00181 bool local_dist;
00183 ReachedMap *_reached;
00185 bool local_reached;
00187 ProcessedMap *_processed;
00189 bool local_processed;
00190
00191 std::vector<typename Graph::Node> _queue;
00192 int _queue_head,_queue_tail,_queue_next_dist;
00193 int _curr_dist;
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 Bfs() {}
00221
00222 public:
00223
00224 typedef Bfs Create;
00225
00227
00229
00230 template <class T>
00231 struct DefPredMapTraits : public Traits {
00232 typedef T PredMap;
00233 static PredMap *createPredMap(const Graph &)
00234 {
00235 throw UninitializedParameter();
00236 }
00237 };
00239
00242 template <class T>
00243 struct DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > {
00244 typedef Bfs< Graph, DefPredMapTraits<T> > Create;
00245 };
00246
00247 template <class T>
00248 struct DefDistMapTraits : public Traits {
00249 typedef T DistMap;
00250 static DistMap *createDistMap(const Graph &)
00251 {
00252 throw UninitializedParameter();
00253 }
00254 };
00256
00259 template <class T>
00260 struct DefDistMap : public Bfs< Graph, DefDistMapTraits<T> > {
00261 typedef Bfs< Graph, DefDistMapTraits<T> > Create;
00262 };
00263
00264 template <class T>
00265 struct DefReachedMapTraits : public Traits {
00266 typedef T ReachedMap;
00267 static ReachedMap *createReachedMap(const Graph &)
00268 {
00269 throw UninitializedParameter();
00270 }
00271 };
00273
00276 template <class T>
00277 struct DefReachedMap : public Bfs< Graph, DefReachedMapTraits<T> > {
00278 typedef Bfs< Graph, DefReachedMapTraits<T> > Create;
00279 };
00280
00281 template <class T>
00282 struct DefProcessedMapTraits : public Traits {
00283 typedef T ProcessedMap;
00284 static ProcessedMap *createProcessedMap(const Graph &G)
00285 {
00286 throw UninitializedParameter();
00287 }
00288 };
00290
00293 template <class T>
00294 struct DefProcessedMap : public Bfs< Graph, DefProcessedMapTraits<T> > {
00295 typedef Bfs< Graph, DefProcessedMapTraits<T> > Create;
00296 };
00297
00298 struct DefGraphProcessedMapTraits : public Traits {
00299 typedef typename Graph::template NodeMap<bool> ProcessedMap;
00300 static ProcessedMap *createProcessedMap(const Graph &G)
00301 {
00302 return new ProcessedMap(G);
00303 }
00304 };
00311 template <class T>
00312 struct DefProcessedMapToBeDefaultMap :
00313 public Bfs< Graph, DefGraphProcessedMapTraits> {
00314 typedef Bfs< Graph, DefGraphProcessedMapTraits> Create;
00315 };
00316
00318
00319 public:
00320
00322
00325 Bfs(const Graph& _G) :
00326 G(&_G),
00327 _pred(NULL), local_pred(false),
00328 _dist(NULL), local_dist(false),
00329 _reached(NULL), local_reached(false),
00330 _processed(NULL), local_processed(false)
00331 { }
00332
00334 ~Bfs()
00335 {
00336 if(local_pred) delete _pred;
00337 if(local_dist) delete _dist;
00338 if(local_reached) delete _reached;
00339 if(local_processed) delete _processed;
00340 }
00341
00343
00349 Bfs &predMap(PredMap &m)
00350 {
00351 if(local_pred) {
00352 delete _pred;
00353 local_pred=false;
00354 }
00355 _pred = &m;
00356 return *this;
00357 }
00358
00360
00366 Bfs &reachedMap(ReachedMap &m)
00367 {
00368 if(local_reached) {
00369 delete _reached;
00370 local_reached=false;
00371 }
00372 _reached = &m;
00373 return *this;
00374 }
00375
00377
00383 Bfs &processedMap(ProcessedMap &m)
00384 {
00385 if(local_processed) {
00386 delete _processed;
00387 local_processed=false;
00388 }
00389 _processed = &m;
00390 return *this;
00391 }
00392
00394
00400 Bfs &distMap(DistMap &m)
00401 {
00402 if(local_dist) {
00403 delete _dist;
00404 local_dist=false;
00405 }
00406 _dist = &m;
00407 return *this;
00408 }
00409
00410 public:
00420
00422
00424
00427 void init()
00428 {
00429 create_maps();
00430 _queue.resize(countNodes(*G));
00431 _queue_head=_queue_tail=0;
00432 _curr_dist=1;
00433 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
00434 _pred->set(u,INVALID);
00435 _reached->set(u,false);
00436 _processed->set(u,false);
00437 }
00438 }
00439
00441
00444 void addSource(Node s)
00445 {
00446 if(!(*_reached)[s])
00447 {
00448 _reached->set(s,true);
00449 _pred->set(s,INVALID);
00450 _dist->set(s,0);
00451 _queue[_queue_head++]=s;
00452 _queue_next_dist=_queue_head;
00453 }
00454 }
00455
00457
00463 Node processNextNode()
00464 {
00465 if(_queue_tail==_queue_next_dist) {
00466 _curr_dist++;
00467 _queue_next_dist=_queue_head;
00468 }
00469 Node n=_queue[_queue_tail++];
00470 _processed->set(n,true);
00471 Node m;
00472 for(OutEdgeIt e(*G,n);e!=INVALID;++e)
00473 if(!(*_reached)[m=G->target(e)]) {
00474 _queue[_queue_head++]=m;
00475 _reached->set(m,true);
00476 _pred->set(m,e);
00477 _dist->set(m,_curr_dist);
00478 }
00479 return n;
00480 }
00481
00483
00488 Node nextNode()
00489 {
00490 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
00491 }
00492
00498 bool emptyQueue() { return _queue_tail==_queue_head; }
00500
00503 int queueSize() { return _queue_head-_queue_tail; }
00504
00506
00519 void start()
00520 {
00521 while ( !emptyQueue() ) processNextNode();
00522 }
00523
00525
00538 void start(Node dest)
00539 {
00540 while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
00541 }
00542
00544
00552 template<class NM>
00553 void start(const NM &nm)
00554 {
00555 while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
00556 }
00557
00559
00573 void run(Node s) {
00574 init();
00575 addSource(s);
00576 start();
00577 }
00578
00580
00592 int run(Node s,Node t) {
00593 init();
00594 addSource(s);
00595 start(t);
00596 return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
00597 }
00598
00600
00606
00608
00610
00617 template<class P>
00618 bool getPath(P &p,Node t)
00619 {
00620 if(reached(t)) {
00621 p.clear();
00622 typename P::Builder b(p);
00623 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
00624 b.pushFront(predEdge(t));
00625 b.commit();
00626 return true;
00627 }
00628 return false;
00629 }
00630
00632
00637 int dist(Node v) const { return (*_dist)[v]; }
00638
00640
00650 Edge predEdge(Node v) const { return (*_pred)[v];}
00651
00653
00664 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
00665 G->source((*_pred)[v]); }
00666
00668
00672 const DistMap &distMap() const { return *_dist;}
00673
00675
00680 const PredMap &predMap() const { return *_pred;}
00681
00683
00689 bool reached(Node v) { return (*_reached)[v]; }
00690
00692 };
00693
00695
00698 template<class GR>
00699 struct BfsWizardDefaultTraits
00700 {
00702 typedef GR Graph;
00710 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
00712
00716 #ifdef DOXYGEN
00717 static PredMap *createPredMap(const GR &g)
00718 #else
00719 static PredMap *createPredMap(const GR &)
00720 #endif
00721 {
00722 return new PredMap();
00723 }
00724
00726
00730 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
00732
00736 #ifdef DOXYGEN
00737 static ProcessedMap *createProcessedMap(const GR &g)
00738 #else
00739 static ProcessedMap *createProcessedMap(const GR &)
00740 #endif
00741 {
00742 return new ProcessedMap();
00743 }
00745
00749 typedef typename Graph::template NodeMap<bool> ReachedMap;
00751
00755 static ReachedMap *createReachedMap(const GR &G)
00756 {
00757 return new ReachedMap(G);
00758 }
00760
00764 typedef NullMap<typename Graph::Node,int> DistMap;
00766
00769 #ifdef DOXYGEN
00770 static DistMap *createDistMap(const GR &g)
00771 #else
00772 static DistMap *createDistMap(const GR &)
00773 #endif
00774 {
00775 return new DistMap();
00776 }
00777 };
00778
00780
00787 template<class GR>
00788 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
00789 {
00790
00791 typedef BfsWizardDefaultTraits<GR> Base;
00792 protected:
00794 typedef typename Base::Graph::Node Node;
00795
00797 void *_g;
00799 void *_reached;
00801 void *_processed;
00803 void *_pred;
00805 void *_dist;
00807 Node _source;
00808
00809 public:
00811
00814 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
00815 _dist(0), _source(INVALID) {}
00816
00818
00824 BfsWizardBase(const GR &g, Node s=INVALID) :
00825 _g((void *)&g), _reached(0), _processed(0), _pred(0),
00826 _dist(0), _source(s) {}
00827
00828 };
00829
00831
00849 template<class TR>
00850 class BfsWizard : public TR
00851 {
00852 typedef TR Base;
00853
00855 typedef typename TR::Graph Graph;
00856
00857 typedef typename Graph::Node Node;
00858
00859 typedef typename Graph::NodeIt NodeIt;
00860
00861 typedef typename Graph::Edge Edge;
00862
00863 typedef typename Graph::OutEdgeIt OutEdgeIt;
00864
00867 typedef typename TR::ReachedMap ReachedMap;
00870 typedef typename TR::ProcessedMap ProcessedMap;
00873 typedef typename TR::PredMap PredMap;
00875 typedef typename TR::DistMap DistMap;
00876
00877 public:
00879 BfsWizard() : TR() {}
00880
00882
00885 BfsWizard(const Graph &g, Node s=INVALID) :
00886 TR(g,s) {}
00887
00889 BfsWizard(const TR &b) : TR(b) {}
00890
00891 ~BfsWizard() {}
00892
00894
00897 void run()
00898 {
00899 if(Base::_source==INVALID) throw UninitializedParameter();
00900 Bfs<Graph,TR> alg(*(Graph*)Base::_g);
00901 if(Base::_reached)
00902 alg.reachedMap(*(ReachedMap*)Base::_reached);
00903 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
00904 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
00905 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
00906 alg.run(Base::_source);
00907 }
00908
00910
00913 void run(Node s)
00914 {
00915 Base::_source=s;
00916 run();
00917 }
00918
00919 template<class T>
00920 struct DefPredMapBase : public Base {
00921 typedef T PredMap;
00922 static PredMap *createPredMap(const Graph &) { return 0; };
00923 DefPredMapBase(const TR &b) : TR(b) {}
00924 };
00925
00932 template<class T>
00933 BfsWizard<DefPredMapBase<T> > predMap(const T &t)
00934 {
00935 Base::_pred=(void *)&t;
00936 return BfsWizard<DefPredMapBase<T> >(*this);
00937 }
00938
00939
00940 template<class T>
00941 struct DefReachedMapBase : public Base {
00942 typedef T ReachedMap;
00943 static ReachedMap *createReachedMap(const Graph &) { return 0; };
00944 DefReachedMapBase(const TR &b) : TR(b) {}
00945 };
00946
00953 template<class T>
00954 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
00955 {
00956 Base::_pred=(void *)&t;
00957 return BfsWizard<DefReachedMapBase<T> >(*this);
00958 }
00959
00960
00961 template<class T>
00962 struct DefProcessedMapBase : public Base {
00963 typedef T ProcessedMap;
00964 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
00965 DefProcessedMapBase(const TR &b) : TR(b) {}
00966 };
00967
00974 template<class T>
00975 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
00976 {
00977 Base::_pred=(void *)&t;
00978 return BfsWizard<DefProcessedMapBase<T> >(*this);
00979 }
00980
00981
00982 template<class T>
00983 struct DefDistMapBase : public Base {
00984 typedef T DistMap;
00985 static DistMap *createDistMap(const Graph &) { return 0; };
00986 DefDistMapBase(const TR &b) : TR(b) {}
00987 };
00988
00995 template<class T>
00996 BfsWizard<DefDistMapBase<T> > distMap(const T &t)
00997 {
00998 Base::_dist=(void *)&t;
00999 return BfsWizard<DefDistMapBase<T> >(*this);
01000 }
01001
01003
01006 BfsWizard<TR> &source(Node s)
01007 {
01008 Base::_source=s;
01009 return *this;
01010 }
01011
01012 };
01013
01015
01031 template<class GR>
01032 BfsWizard<BfsWizardBase<GR> >
01033 bfs(const GR &g,typename GR::Node s=INVALID)
01034 {
01035 return BfsWizard<BfsWizardBase<GR> >(g,s);
01036 }
01037
01038 }
01039
01040 #endif
01041