00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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
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 }
00950
00951 #endif
00952