bfs.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_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     //\e
00857     typedef typename Graph::Node Node;
00858     //\e
00859     typedef typename Graph::NodeIt NodeIt;
00860     //\e
00861     typedef typename Graph::Edge Edge;
00862     //\e
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 } //END OF NAMESPACE LEMON
01039 
01040 #endif
01041 

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