bellman_ford.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_BELMANN_FORD_H
00020 #define LEMON_BELMANN_FORD_H
00021 
00026 
00027 #include <lemon/list_graph.h>
00028 #include <lemon/invalid.h>
00029 #include <lemon/error.h>
00030 #include <lemon/maps.h>
00031 
00032 #include <limits>
00033 
00034 namespace lemon {
00035 
00043   template <
00044     typename Value, 
00045     bool has_infinity = std::numeric_limits<Value>::has_infinity>
00046   struct BellmanFordDefaultOperationTraits {
00048     static Value zero() {
00049       return static_cast<Value>(0);
00050     }
00052     static Value infinity() {
00053       return std::numeric_limits<Value>::infinity();
00054     }
00056     static Value plus(const Value& left, const Value& right) {
00057       return left + right;
00058     }
00060     static bool less(const Value& left, const Value& right) {
00061       return left < right;
00062     }
00063   };
00064 
00065   template <typename Value>
00066   struct BellmanFordDefaultOperationTraits<Value, false> {
00067     static Value zero() {
00068       return static_cast<Value>(0);
00069     }
00070     static Value infinity() {
00071       return std::numeric_limits<Value>::max();
00072     }
00073     static Value plus(const Value& left, const Value& right) {
00074       if (left == infinity() || right == infinity()) return infinity();
00075       return left + right;
00076     }
00077     static bool less(const Value& left, const Value& right) {
00078       return left < right;
00079     }
00080   };
00081   
00087   template<class _Graph, class _LengthMap>
00088   struct BellmanFordDefaultTraits {
00090     typedef _Graph Graph;
00091 
00096     typedef _LengthMap LengthMap;
00097 
00098     // The type of the length of the edges.
00099     typedef typename _LengthMap::Value Value;
00100 
00106     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
00107  
00115     typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
00116 
00121     static PredMap *createPredMap(const _Graph& graph) {
00122       return new PredMap(graph);
00123     }
00124 
00130     typedef typename Graph::template NodeMap<typename _LengthMap::Value> 
00131     DistMap;
00132 
00138     static DistMap *createDistMap(const _Graph& graph) {
00139       return new DistMap(graph);
00140     }
00141 
00142   };
00143   
00177 
00178 #ifdef DOXYGEN
00179   template <typename _Graph, typename _LengthMap, typename _Traits>
00180 #else
00181   template <typename _Graph=ListGraph,
00182             typename _LengthMap=typename _Graph::template EdgeMap<int>,
00183             typename _Traits=BellmanFordDefaultTraits<_Graph,_LengthMap> >
00184 #endif
00185   class BellmanFord {
00186   public:
00187     
00192 
00193     class UninitializedParameter : public lemon::UninitializedParameter {
00194     public:
00195       virtual const char* exceptionName() const {
00196         return "lemon::BellmanFord::UninitializedParameter";
00197       }
00198     };
00199 
00200     typedef _Traits Traits;
00202     typedef typename _Traits::Graph Graph;
00203 
00204     typedef typename Graph::Node Node;
00205     typedef typename Graph::NodeIt NodeIt;
00206     typedef typename Graph::Edge Edge;
00207     typedef typename Graph::OutEdgeIt OutEdgeIt;
00208     
00210     typedef typename _Traits::LengthMap::Value Value;
00212     typedef typename _Traits::LengthMap LengthMap;
00215     typedef typename _Traits::PredMap PredMap;
00217     typedef typename _Traits::DistMap DistMap;
00219     typedef typename _Traits::OperationTraits OperationTraits;
00220   private:
00222     const Graph *graph;
00224     const LengthMap *length;
00226     PredMap *_pred;
00228     bool local_pred;
00230     DistMap *_dist;
00232     bool local_dist;
00233 
00234     typedef typename Graph::template NodeMap<bool> MaskMap;
00235     MaskMap *_mask;
00236 
00237     std::vector<Node> _process;
00238 
00240     void create_maps() {
00241       if(!_pred) {
00242         local_pred = true;
00243         _pred = Traits::createPredMap(*graph);
00244       }
00245       if(!_dist) {
00246         local_dist = true;
00247         _dist = Traits::createDistMap(*graph);
00248       }
00249       _mask = new MaskMap(*graph, false);
00250     }
00251     
00252   public :
00253  
00254     typedef BellmanFord Create;
00255 
00257 
00259 
00260     template <class T>
00261     struct DefPredMapTraits : public Traits {
00262       typedef T PredMap;
00263       static PredMap *createPredMap(const Graph&) {
00264         throw UninitializedParameter();
00265       }
00266     };
00267 
00272     template <class T>
00273     struct DefPredMap 
00274       : public BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > {
00275       typedef BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
00276     };
00277     
00278     template <class T>
00279     struct DefDistMapTraits : public Traits {
00280       typedef T DistMap;
00281       static DistMap *createDistMap(const Graph& graph) {
00282         throw UninitializedParameter();
00283       }
00284     };
00285 
00291     template <class T>
00292     struct DefDistMap 
00293       : public BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > {
00294       typedef BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
00295     };
00296     
00297     template <class T>
00298     struct DefOperationTraitsTraits : public Traits {
00299       typedef T OperationTraits;
00300     };
00301     
00307     template <class T>
00308     struct DefOperationTraits
00309       : public BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
00310       typedef BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
00311       Create;
00312     };
00313     
00315 
00316   protected:
00317     
00318     BellmanFord() {}
00319 
00320   public:      
00321     
00326     BellmanFord(const Graph& _graph, const LengthMap& _length) :
00327       graph(&_graph), length(&_length),
00328       _pred(0), local_pred(false),
00329       _dist(0), local_dist(false) {}
00330     
00332     ~BellmanFord() {
00333       if(local_pred) delete _pred;
00334       if(local_dist) delete _dist;
00335       delete _mask;
00336     }
00337 
00342     BellmanFord &lengthMap(const LengthMap &m) {
00343       length = &m;
00344       return *this;
00345     }
00346 
00354     BellmanFord &predMap(PredMap &m) {
00355       if(local_pred) {
00356         delete _pred;
00357         local_pred=false;
00358       }
00359       _pred = &m;
00360       return *this;
00361     }
00362 
00370     BellmanFord &distMap(DistMap &m) {
00371       if(local_dist) {
00372         delete _dist;
00373         local_dist=false;
00374       }
00375       _dist = &m;
00376       return *this;
00377     }
00378 
00388 
00390 
00394     void init(const Value value = OperationTraits::infinity()) {
00395       create_maps();
00396       for (NodeIt it(*graph); it != INVALID; ++it) {
00397         _pred->set(it, INVALID);
00398         _dist->set(it, value);
00399       }
00400       _process.clear();
00401       if (OperationTraits::less(value, OperationTraits::infinity())) {
00402         for (NodeIt it(*graph); it != INVALID; ++it) {
00403           _process.push_back(it);
00404           _mask->set(it, true);
00405         }
00406       }
00407     }
00408     
00413     void addSource(Node source, Value dst = OperationTraits::zero()) {
00414       _dist->set(source, dst);
00415       if (!(*_mask)[source]) {
00416         _process.push_back(source);
00417         _mask->set(source, true);
00418       }
00419     }
00420 
00428     bool processNextRound() {
00429       for (int i = 0; i < (int)_process.size(); ++i) {
00430         _mask->set(_process[i], false);
00431       }
00432       std::vector<Node> nextProcess;
00433       std::vector<Value> values(_process.size());
00434       for (int i = 0; i < (int)_process.size(); ++i) {
00435         values[i] = (*_dist)[_process[i]];
00436       }
00437       for (int i = 0; i < (int)_process.size(); ++i) {
00438         for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
00439           Node target = graph->target(it);
00440           Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
00441           if (OperationTraits::less(relaxed, (*_dist)[target])) {
00442             _pred->set(target, it);
00443             _dist->set(target, relaxed);
00444             if (!(*_mask)[target]) {
00445               _mask->set(target, true);
00446               nextProcess.push_back(target);
00447             }
00448           }       
00449         }
00450       }
00451       _process.swap(nextProcess);
00452       return _process.empty();
00453     }
00454 
00464     bool processNextWeakRound() {
00465       for (int i = 0; i < (int)_process.size(); ++i) {
00466         _mask->set(_process[i], false);
00467       }
00468       std::vector<Node> nextProcess;
00469       for (int i = 0; i < (int)_process.size(); ++i) {
00470         for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
00471           Node target = graph->target(it);
00472           Value relaxed = 
00473             OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
00474           if (OperationTraits::less(relaxed, (*_dist)[target])) {
00475             _pred->set(target, it);
00476             _dist->set(target, relaxed);
00477             if (!(*_mask)[target]) {
00478               _mask->set(target, true);
00479               nextProcess.push_back(target);
00480             }
00481           }       
00482         }
00483       }
00484       _process.swap(nextProcess);
00485       return _process.empty();
00486     }
00487 
00498     void start() {
00499       int num = countNodes(*graph) - 1;
00500       for (int i = 0; i < num; ++i) {
00501         if (processNextWeakRound()) break;
00502       }
00503     }
00504 
00516     bool checkedStart() {
00517       int num = countNodes(*graph);
00518       for (int i = 0; i < num; ++i) {
00519         if (processNextWeakRound()) return true;
00520       }
00521       return false;
00522     }
00523 
00534     void limitedStart(int length) {
00535       for (int i = 0; i < length; ++i) {
00536         if (processNextRound()) break;
00537       }
00538     }
00539     
00554     void run(Node s) {
00555       init();
00556       addSource(s);
00557       start();
00558     }
00559     
00575     void run(Node s, int len) {
00576       init();
00577       addSource(s);
00578       limitedStart(len);
00579     }
00580     
00582 
00588     
00590 
00600     template <typename Path>
00601     bool getPath(Path &p, Node t) {
00602       if(reached(t)) {
00603         p.clear();
00604         typename Path::Builder b(p);
00605         for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
00606           b.pushFront(predEdge(t));
00607         b.commit();
00608         return true;
00609       }
00610       return false;
00611     }
00612           
00619     Value dist(Node v) const { return (*_dist)[v]; }
00620 
00630     Edge predEdge(Node v) const { return (*_pred)[v]; }
00631 
00640     Node predNode(Node v) const { 
00641       return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]); 
00642     }
00643     
00648     const DistMap &distMap() const { return *_dist;}
00649  
00655     const PredMap &predMap() const { return *_pred; }
00656  
00662     bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
00663     
00665   };
00666  
00672   template <typename _Graph, typename _LengthMap>
00673   struct BellmanFordWizardDefaultTraits {
00675     typedef _Graph Graph;
00676 
00681     typedef _LengthMap LengthMap;
00682 
00684     typedef typename _LengthMap::Value Value;
00685 
00691     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
00692 
00699     typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
00700 
00704     static PredMap *createPredMap(const _Graph &) {
00705       return new PredMap();
00706     }
00711     typedef NullMap<typename Graph::Node, Value> DistMap;
00715     static DistMap *createDistMap(const _Graph &) {
00716       return new DistMap();
00717     }
00718   };
00719   
00729   template<class _Graph,class _LengthMap>
00730   class BellmanFordWizardBase 
00731     : public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> {
00732 
00733     typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
00734   protected:
00736     typedef typename Base::Graph::Node Node;
00737 
00739     void *_graph;
00741     void *_length;
00743     void *_pred;
00745     void *_dist;
00747     Node _source;
00748 
00749     public:
00751     
00754     BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
00755                            _dist(0), _source(INVALID) {}
00756 
00758     
00765     BellmanFordWizardBase(const _Graph& graph, 
00766                           const _LengthMap& length, 
00767                           Node source = INVALID) :
00768       _graph((void *)&graph), _length((void *)&length), _pred(0),
00769       _dist(0), _source(source) {}
00770 
00771   };
00772   
00774 
00792   template<class _Traits>
00793   class BellmanFordWizard : public _Traits {
00794     typedef _Traits Base;
00795 
00797     typedef typename _Traits::Graph Graph;
00798 
00799     typedef typename Graph::Node Node;
00800     typedef typename Graph::NodeIt NodeIt;
00801     typedef typename Graph::Edge Edge;
00802     typedef typename Graph::OutEdgeIt EdgeIt;
00803     
00805     typedef typename _Traits::LengthMap LengthMap;
00806 
00808     typedef typename LengthMap::Value Value;
00809 
00812     typedef typename _Traits::PredMap PredMap;
00813 
00815     typedef typename _Traits::DistMap DistMap;
00816 
00817   public:
00819     BellmanFordWizard() : _Traits() {}
00820 
00825     BellmanFordWizard(const Graph& graph, const LengthMap& length, 
00826                       Node source = INVALID) 
00827       : _Traits(graph, length, source) {}
00828 
00830     BellmanFordWizard(const _Traits &b) : _Traits(b) {}
00831 
00832     ~BellmanFordWizard() {}
00833 
00838     void run() {
00839       if(Base::_source == INVALID) throw UninitializedParameter();
00840       BellmanFord<Graph,LengthMap,_Traits> 
00841         bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
00842       if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
00843       if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
00844       bf.run(Base::_source);
00845     }
00846 
00851     void run(Node source) {
00852       Base::_source = source;
00853       run();
00854     }
00855 
00856     template<class T>
00857     struct DefPredMapBase : public Base {
00858       typedef T PredMap;
00859       static PredMap *createPredMap(const Graph &) { return 0; };
00860       DefPredMapBase(const _Traits &b) : _Traits(b) {}
00861     };
00862     
00869     template<class T>
00870     BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) 
00871     {
00872       Base::_pred=(void *)&t;
00873       return BellmanFordWizard<DefPredMapBase<T> >(*this);
00874     }
00875     
00876     template<class T>
00877     struct DefDistMapBase : public Base {
00878       typedef T DistMap;
00879       static DistMap *createDistMap(const Graph &) { return 0; };
00880       DefDistMapBase(const _Traits &b) : _Traits(b) {}
00881     };
00882     
00889     template<class T>
00890     BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
00891       Base::_dist=(void *)&t;
00892       return BellmanFordWizard<DefDistMapBase<T> >(*this);
00893     }
00894 
00895     template<class T>
00896     struct DefOperationTraitsBase : public Base {
00897       typedef T OperationTraits;
00898       DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
00899     };
00900     
00907     template<class T>
00908     BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
00909       return BellmanFordWizard<DefDistMapBase<T> >(*this);
00910     }
00911     
00916     BellmanFordWizard<_Traits>& source(Node source) {
00917       Base::_source = source;
00918       return *this;
00919     }
00920     
00921   };
00922   
00940   template<class _Graph, class _LengthMap>
00941   BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
00942   bellmanFord(const _Graph& graph,
00943               const _LengthMap& length, 
00944               typename _Graph::Node source = INVALID) {
00945     return BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
00946       (graph, length, source);
00947   }
00948 
00949 } //END OF NAMESPACE LEMON
00950 
00951 #endif
00952 

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