Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

dijkstra.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00017 #ifndef LEMON_DIJKSTRA_H
00018 #define LEMON_DIJKSTRA_H
00019 
00023 
00024 #include <lemon/list_graph.h>
00025 #include <lemon/bin_heap.h>
00026 #include <lemon/invalid.h>
00027 #include <lemon/error.h>
00028 #include <lemon/maps.h>
00029 
00030 namespace lemon {
00031 
00032 
00033   
00035 
00039   template<class GR, class LM>
00040   struct DijkstraDefaultTraits
00041   {
00043     typedef GR Graph;
00045 
00048     typedef LM LengthMap;
00049     //The type of the length of the edges.
00050     typedef typename LM::Value Value;
00052 
00057     typedef BinHeap<typename Graph::Node,
00058                     typename LM::Value,
00059                     typename GR::template NodeMap<int>,
00060                     std::less<Value> > Heap;
00061 
00069     typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
00071  
00075     static PredMap *createPredMap(const GR &G) 
00076     {
00077       return new PredMap(G);
00078     }
00086     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
00088     
00092     static PredNodeMap *createPredNodeMap(const GR &G)
00093     {
00094       return new PredNodeMap();
00095     }
00096 
00098  
00104     typedef NullMap<typename Graph::Node,bool> ReachedMap;
00106  
00110     static ReachedMap *createReachedMap(const GR &G)
00111     {
00112       return new ReachedMap();
00113     }
00115  
00119     typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
00121  
00124     static DistMap *createDistMap(const GR &G)
00125     {
00126       return new DistMap(G);
00127     }
00128   };
00129   
00131   
00163 
00164 #ifdef DOXYGEN
00165   template <typename GR,
00166             typename LM,
00167             typename TR>
00168 #else
00169   template <typename GR=ListGraph,
00170             typename LM=typename GR::template EdgeMap<int>,
00171             typename TR=DijkstraDefaultTraits<GR,LM> >
00172 #endif
00173   class Dijkstra {
00174   public:
00181     class UninitializedParameter : public lemon::UninitializedParameter {
00182     public:
00183       virtual const char* exceptionName() const {
00184         return "lemon::Dijsktra::UninitializedParameter";
00185       }
00186     };
00187 
00188     typedef TR Traits;
00190     typedef typename TR::Graph Graph;
00192     typedef typename Graph::Node Node;
00194     typedef typename Graph::NodeIt NodeIt;
00196     typedef typename Graph::Edge Edge;
00198     typedef typename Graph::OutEdgeIt OutEdgeIt;
00199     
00201     typedef typename TR::LengthMap::Value Value;
00203     typedef typename TR::LengthMap LengthMap;
00206     typedef typename TR::PredMap PredMap;
00209     typedef typename TR::PredNodeMap PredNodeMap;
00211     typedef typename TR::ReachedMap ReachedMap;
00213     typedef typename TR::DistMap DistMap;
00215     typedef typename TR::Heap Heap;
00216   private:
00218     const Graph *G;
00220     const LengthMap *length;
00222     PredMap *_pred;
00224     bool local_pred;
00226     PredNodeMap *_predNode;
00228     bool local_predNode;
00230     DistMap *_dist;
00232     bool local_dist;
00234     ReachedMap *_reached;
00236     bool local_reached;
00237 
00239     Node source;
00240 
00242     
00245     void create_maps() 
00246     {
00247       if(!_pred) {
00248         local_pred = true;
00249         _pred = Traits::createPredMap(*G);
00250       }
00251       if(!_predNode) {
00252         local_predNode = true;
00253         _predNode = Traits::createPredNodeMap(*G);
00254       }
00255       if(!_dist) {
00256         local_dist = true;
00257         _dist = Traits::createDistMap(*G);
00258       }
00259       if(!_reached) {
00260         local_reached = true;
00261         _reached = Traits::createReachedMap(*G);
00262       }
00263     }
00264     
00265   public :
00266  
00268 
00270 
00271     template <class T>
00272     struct DefPredMapTraits : public Traits {
00273       typedef T PredMap;
00274       static PredMap *createPredMap(const Graph &G) 
00275       {
00276         throw UninitializedParameter();
00277       }
00278     };
00280 
00283     template <class T>
00284     class DefPredMap : public Dijkstra< Graph,
00285                                         LengthMap,
00286                                         DefPredMapTraits<T> > { };
00287     
00288     template <class T>
00289     struct DefPredNodeMapTraits : public Traits {
00290       typedef T PredNodeMap;
00291       static PredNodeMap *createPredNodeMap(const Graph &G) 
00292       {
00293         throw UninitializedParameter();
00294       }
00295     };
00297 
00300     template <class T>
00301     class DefPredNodeMap : public Dijkstra< Graph,
00302                                             LengthMap,
00303                                             DefPredNodeMapTraits<T> > { };
00304     
00305     template <class T>
00306     struct DefDistMapTraits : public Traits {
00307       typedef T DistMap;
00308       static DistMap *createDistMap(const Graph &G) 
00309       {
00310         throw UninitializedParameter();
00311       }
00312     };
00314 
00317     template <class T>
00318     class DefDistMap : public Dijkstra< Graph,
00319                                         LengthMap,
00320                                         DefDistMapTraits<T> > { };
00321     
00322     template <class T>
00323     struct DefReachedMapTraits : public Traits {
00324       typedef T ReachedMap;
00325       static ReachedMap *createReachedMap(const Graph &G) 
00326       {
00327         throw UninitializedParameter();
00328       }
00329     };
00331 
00334     template <class T>
00335     class DefReachedMap : public Dijkstra< Graph,
00336                                         LengthMap,
00337                                         DefReachedMapTraits<T> > { };
00338     
00339     struct DefGraphReachedMapTraits : public Traits {
00340       typedef typename Graph::NodeMap<bool> ReachedMap;
00341       static ReachedMap *createReachedMap(const Graph &G) 
00342       {
00343         return new ReachedMap(G);
00344       }
00345     };
00352     template <class T>
00353     class DefReachedMapToBeDefaultMap :
00354       public Dijkstra< Graph,
00355                        LengthMap,
00356                        DefGraphReachedMapTraits> { };
00357     
00359 
00360 
00361   private:
00362     typename Graph::template NodeMap<int> _heap_map;
00363     Heap _heap;
00364   public:      
00365     
00367     
00370     Dijkstra(const Graph& _G, const LengthMap& _length) :
00371       G(&_G), length(&_length),
00372       _pred(NULL), local_pred(false),
00373       _predNode(NULL), local_predNode(false),
00374       _dist(NULL), local_dist(false),
00375       _reached(NULL), local_reached(false),
00376       _heap_map(*G,-1),_heap(_heap_map)
00377     { }
00378     
00380     ~Dijkstra() 
00381     {
00382       if(local_pred) delete _pred;
00383       if(local_predNode) delete _predNode;
00384       if(local_dist) delete _dist;
00385       if(local_reached) delete _reached;
00386     }
00387 
00389 
00392     Dijkstra &lengthMap(const LengthMap &m) 
00393     {
00394       length = &m;
00395       return *this;
00396     }
00397 
00399 
00405     Dijkstra &predMap(PredMap &m) 
00406     {
00407       if(local_pred) {
00408         delete _pred;
00409         local_pred=false;
00410       }
00411       _pred = &m;
00412       return *this;
00413     }
00414 
00416 
00422     Dijkstra &predNodeMap(PredNodeMap &m) 
00423     {
00424       if(local_predNode) {
00425         delete _predNode;
00426         local_predNode=false;
00427       }
00428       _predNode = &m;
00429       return *this;
00430     }
00431 
00433 
00439     Dijkstra &distMap(DistMap &m) 
00440     {
00441       if(local_dist) {
00442         delete _dist;
00443         local_dist=false;
00444       }
00445       _dist = &m;
00446       return *this;
00447     }
00448 
00449   private:
00450     void finalizeNodeData(Node v,Value dst)
00451     {
00452       _reached->set(v,true);
00453       _dist->set(v, dst);
00454       _predNode->set(v,G->source((*_pred)[v]));
00455     }
00456 
00457   public:
00466 
00468 
00470 
00474     void init()
00475     {
00476       create_maps();
00477       
00478       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
00479         _pred->set(u,INVALID);
00480         _predNode->set(u,INVALID);
00482         _heap_map.set(u,Heap::PRE_HEAP);
00483       }
00484     }
00485     
00487 
00495     void addSource(Node s,Value dst=0)
00496     {
00497       source = s;
00498       if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
00499       else if(_heap[s]<dst) {
00500         _heap.push(s,dst);
00501         _pred->set(s,INVALID);
00502       }
00503     }
00504     
00506 
00510     void processNextNode()
00511     {
00512       Node v=_heap.top(); 
00513       Value oldvalue=_heap[v];
00514       _heap.pop();
00515       finalizeNodeData(v,oldvalue);
00516       
00517       for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
00518         Node w=G->target(e); 
00519         switch(_heap.state(w)) {
00520         case Heap::PRE_HEAP:
00521           _heap.push(w,oldvalue+(*length)[e]); 
00522           _pred->set(w,e);
00523 //        _predNode->set(w,v);
00524           break;
00525         case Heap::IN_HEAP:
00526           if ( oldvalue+(*length)[e] < _heap[w] ) {
00527             _heap.decrease(w, oldvalue+(*length)[e]); 
00528             _pred->set(w,e);
00529 //          _predNode->set(w,v);
00530           }
00531           break;
00532         case Heap::POST_HEAP:
00533           break;
00534         }
00535       }
00536     }
00537 
00539 
00542     bool emptyHeap() { return heap.empty(); }
00544 
00547     int heapSize() { return heap.size(); }
00548     
00550 
00563     void start()
00564     {
00565       while ( !_heap.empty() ) processNextNode();
00566     }
00567     
00569 
00582     void start(Node dest)
00583     {
00584       while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
00585       if ( _heap.top()==dest ) finalizeNodeData(_heap.top());
00586     }
00587     
00589 
00597     template<class NM>
00598     void start(const NM &nm)
00599     {
00600       while ( !_heap.empty() && !mn[_heap.top()] ) processNextNode();
00601       if ( !_heap.empty() ) finalizeNodeData(_heap.top());
00602     }
00603     
00605     
00619     void run(Node s) {
00620       init();
00621       addSource(s);
00622       start();
00623     }
00624     
00626     
00638     Value run(Node s,Node t) {
00639       init();
00640       addSource(s);
00641       start(t);
00642       return (*_pred)[t]==INVALID?0:(*_dist)[t];
00643     }
00644     
00646 
00652     
00654 
00656 
00661     Value dist(Node v) const { return (*_dist)[v]; }
00662 
00664 
00673     Edge pred(Node v) const { return (*_pred)[v]; }
00674 
00676 
00683     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
00684                                   G->source((*_pred)[v]); }
00685     
00687 
00690     const DistMap &distMap() const { return *_dist;}
00691  
00693 
00697     const PredMap &predMap() const { return *_pred;}
00698  
00700 
00704     const PredNodeMap &predNodeMap() const { return *_predNode;}
00705 
00707 
00713     bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
00714     
00716   };
00717 
00719 
00726   template<class GR,class LM>
00727   class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
00728   {
00729 
00730     typedef DijkstraDefaultTraits<GR,LM> Base;
00731   protected:
00733     void *_g;
00735     void *_length;
00737     void *_pred;
00739     void *_predNode;
00741     void *_dist;
00743     void *_source;
00744 
00746     typedef typename Base::Graph::Node Node;
00747 
00748     public:
00750     
00753     DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
00754                        _dist(0), _source(INVALID) {}
00755 
00757     
00764     DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
00765       _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
00766                   _dist(0), _source((void *)&s) {}
00767 
00768   };
00769   
00771 
00790   template<class TR>
00791   class DijkstraWizard : public TR
00792   {
00793     typedef TR Base;
00794 
00796     typedef typename TR::Graph Graph;
00797     //\e
00798     typedef typename Graph::Node Node;
00799     //\e
00800     typedef typename Graph::NodeIt NodeIt;
00801     //\e
00802     typedef typename Graph::Edge Edge;
00803     //\e
00804     typedef typename Graph::OutEdgeIt OutEdgeIt;
00805     
00807     typedef typename TR::LengthMap LengthMap;
00809     typedef typename LengthMap::Value Value;
00812     typedef typename TR::PredMap PredMap;
00815     typedef typename TR::PredNodeMap PredNodeMap;
00817     typedef typename TR::DistMap DistMap;
00818 
00820     typedef typename TR::Heap Heap;
00821 public:
00823     DijkstraWizard() : TR() {}
00824 
00826 
00829     DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
00830       TR(g,l,s) {}
00831 
00833     DijkstraWizard(const TR &b) : TR(b) {}
00834 
00835     ~DijkstraWizard() {}
00836 
00838     
00841     void run()
00842     {
00843       if(_source==0) throw UninitializedParameter();
00844       Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
00845       if(_pred) Dij.predMap(*(PredMap*)_pred);
00846       if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
00847       if(_dist) Dij.distMap(*(DistMap*)_dist);
00848       Dij.run(*(Node*)_source);
00849     }
00850 
00852 
00855     void run(Node s)
00856     {
00857       _source=(void *)&s;
00858       run();
00859     }
00860 
00861     template<class T>
00862     struct DefPredMapBase : public Base {
00863       typedef T PredMap;
00864       static PredMap *createPredMap(const Graph &G) { return 0; };
00865       DefPredMapBase(const Base &b) : Base(b) {}
00866     };
00867     
00874     template<class T>
00875     DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) 
00876     {
00877       _pred=(void *)&t;
00878       return DijkstraWizard<DefPredMapBase<T> >(*this);
00879     }
00880     
00881 
00882     template<class T>
00883     struct DefPredNodeMapBase : public Base {
00884       typedef T PredNodeMap;
00885       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
00886       DefPredNodeMapBase(const Base &b) : Base(b) {}
00887     };
00888     
00895     template<class T>
00896     DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 
00897     {
00898       _predNode=(void *)&t;
00899       return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
00900     }
00901    
00902     template<class T>
00903     struct DefDistMapBase : public Base {
00904       typedef T DistMap;
00905       static DistMap *createDistMap(const Graph &G) { return 0; };
00906       DefDistMapBase(const Base &b) : Base(b) {}
00907     };
00908     
00915     template<class T>
00916     DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) 
00917     {
00918       _dist=(void *)&t;
00919       return DijkstraWizard<DefDistMapBase<T> >(*this);
00920     }
00921     
00923 
00926     DijkstraWizard<TR> &source(Node s) 
00927     {
00928       source=(void *)&s;
00929       return *this;
00930     }
00931     
00932   };
00933   
00935 
00939   template<class GR, class LM>
00940   DijkstraWizard<DijkstraWizardBase<GR,LM> >
00941   dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
00942   {
00943     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
00944   }
00945 
00947   
00948 } //END OF NAMESPACE LEMON
00949 
00950 #endif
00951 

Generated on Sat Mar 19 10:58:39 2005 for LEMON by  doxygen 1.4.1