00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_JOHNSON_H
00020 #define LEMON_JOHNSON_H
00021
00026
00027 #include <lemon/list_graph.h>
00028 #include <lemon/graph_utils.h>
00029 #include <lemon/dijkstra.h>
00030 #include <lemon/bellman_ford.h>
00031 #include <lemon/invalid.h>
00032 #include <lemon/error.h>
00033 #include <lemon/maps.h>
00034 #include <lemon/matrix_maps.h>
00035
00036 #include <limits>
00037
00038 namespace lemon {
00039
00047 template <
00048 typename Value,
00049 bool has_infinity = std::numeric_limits<Value>::has_infinity>
00050 struct JohnsonDefaultOperationTraits {
00052 static Value zero() {
00053 return static_cast<Value>(0);
00054 }
00056 static Value infinity() {
00057 return std::numeric_limits<Value>::infinity();
00058 }
00060 static Value plus(const Value& left, const Value& right) {
00061 return left + right;
00062 }
00064 static bool less(const Value& left, const Value& right) {
00065 return left < right;
00066 }
00067 };
00068
00069 template <typename Value>
00070 struct JohnsonDefaultOperationTraits<Value, false> {
00071 static Value zero() {
00072 return static_cast<Value>(0);
00073 }
00074 static Value infinity() {
00075 return std::numeric_limits<Value>::max();
00076 }
00077 static Value plus(const Value& left, const Value& right) {
00078 if (left == infinity() || right == infinity()) return infinity();
00079 return left + right;
00080 }
00081 static bool less(const Value& left, const Value& right) {
00082 return left < right;
00083 }
00084 };
00085
00091 template<class _Graph, class _LengthMap>
00092 struct JohnsonDefaultTraits {
00094 typedef _Graph Graph;
00095
00100 typedef _LengthMap LengthMap;
00101
00102
00103 typedef typename _LengthMap::Value Value;
00104
00110 typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
00111
00113
00116 typedef typename Graph::template NodeMap<int> HeapCrossRef;
00117
00119
00123 static HeapCrossRef *createHeapCrossRef(const Graph& graph) {
00124 return new HeapCrossRef(graph);
00125 }
00126
00128
00133 typedef BinHeap<typename Graph::Node, typename LengthMap::Value,
00134 HeapCrossRef, std::less<Value> > Heap;
00135
00137
00140 static Heap *createHeap(HeapCrossRef& crossRef) {
00141 return new Heap(crossRef);
00142 }
00143
00150 typedef DynamicMatrixMap<Graph, typename Graph::Node,
00151 typename Graph::Edge> PredMap;
00152
00158 static PredMap *createPredMap(const Graph& graph) {
00159 return new PredMap(graph);
00160 }
00161
00167 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
00168
00174 static DistMap *createDistMap(const _Graph& graph) {
00175 return new DistMap(graph);
00176 }
00177
00178 };
00179
00219
00220 #ifdef DOXYGEN
00221 template <typename _Graph, typename _LengthMap, typename _Traits>
00222 #else
00223 template <typename _Graph=ListGraph,
00224 typename _LengthMap=typename _Graph::template EdgeMap<int>,
00225 typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> >
00226 #endif
00227 class Johnson {
00228 public:
00229
00234
00235 class UninitializedParameter : public lemon::UninitializedParameter {
00236 public:
00237 virtual const char* exceptionName() const {
00238 return "lemon::Johnson::UninitializedParameter";
00239 }
00240 };
00241
00242 typedef _Traits Traits;
00244 typedef typename _Traits::Graph Graph;
00245
00246 typedef typename Graph::Node Node;
00247 typedef typename Graph::NodeIt NodeIt;
00248 typedef typename Graph::Edge Edge;
00249 typedef typename Graph::EdgeIt EdgeIt;
00250
00252 typedef typename _Traits::LengthMap::Value Value;
00254 typedef typename _Traits::LengthMap LengthMap;
00258 typedef typename _Traits::PredMap PredMap;
00261 typedef typename _Traits::DistMap DistMap;
00263 typedef typename _Traits::OperationTraits OperationTraits;
00265 typedef typename _Traits::HeapCrossRef HeapCrossRef;
00267 typedef typename _Traits::Heap Heap;
00268 private:
00270 const Graph *graph;
00272 const LengthMap *length;
00274 PredMap *_pred;
00276 bool local_pred;
00278 DistMap *_dist;
00280 bool local_dist;
00282 HeapCrossRef *_heap_cross_ref;
00284 bool local_heap_cross_ref;
00286 Heap *_heap;
00288 bool local_heap;
00289
00291 void create_maps() {
00292 if(!_pred) {
00293 local_pred = true;
00294 _pred = Traits::createPredMap(*graph);
00295 }
00296 if(!_dist) {
00297 local_dist = true;
00298 _dist = Traits::createDistMap(*graph);
00299 }
00300 if (!_heap_cross_ref) {
00301 local_heap_cross_ref = true;
00302 _heap_cross_ref = Traits::createHeapCrossRef(*graph);
00303 }
00304 if (!_heap) {
00305 local_heap = true;
00306 _heap = Traits::createHeap(*_heap_cross_ref);
00307 }
00308 }
00309
00310 public :
00311
00313
00315
00316 template <class T>
00317 struct DefPredMapTraits : public Traits {
00318 typedef T PredMap;
00319 static PredMap *createPredMap(const Graph& graph) {
00320 throw UninitializedParameter();
00321 }
00322 };
00323
00328 template <class T>
00329 struct DefPredMap
00330 : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {
00331 typedef Johnson< Graph, LengthMap, DefPredMapTraits<T> > Create;
00332 };
00333
00334 template <class T>
00335 struct DefDistMapTraits : public Traits {
00336 typedef T DistMap;
00337 static DistMap *createDistMap(const Graph& graph) {
00338 throw UninitializedParameter();
00339 }
00340 };
00346 template <class T>
00347 struct DefDistMap
00348 : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {
00349 typedef Johnson< Graph, LengthMap, DefDistMapTraits<T> > Create;
00350 };
00351
00352 template <class T>
00353 struct DefOperationTraitsTraits : public Traits {
00354 typedef T OperationTraits;
00355 };
00356
00362 template <class T>
00363 struct DefOperationTraits
00364 : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {
00365 typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
00366 };
00367
00368 template <class H, class CR>
00369 struct DefHeapTraits : public Traits {
00370 typedef CR HeapCrossRef;
00371 typedef H Heap;
00372 static HeapCrossRef *createHeapCrossRef(const Graph &) {
00373 throw UninitializedParameter();
00374 }
00375 static Heap *createHeap(HeapCrossRef &)
00376 {
00377 throw UninitializedParameter();
00378 }
00379 };
00382
00386 template <class H, class CR = typename Graph::template NodeMap<int> >
00387 struct DefHeap
00388 : public Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > {
00389 typedef Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
00390 };
00391
00392 template <class H, class CR>
00393 struct DefStandardHeapTraits : public Traits {
00394 typedef CR HeapCrossRef;
00395 typedef H Heap;
00396 static HeapCrossRef *createHeapCrossRef(const Graph &G) {
00397 return new HeapCrossRef(G);
00398 }
00399 static Heap *createHeap(HeapCrossRef &R)
00400 {
00401 return new Heap(R);
00402 }
00403 };
00406
00411 template <class H, class CR = typename Graph::template NodeMap<int> >
00412 struct DefStandardHeap
00413 : public Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > {
00414 typedef Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> >
00415 Create;
00416 };
00417
00419
00420 protected:
00421
00422 Johnson() {}
00423
00424 public:
00425
00426 typedef Johnson Create;
00427
00432 Johnson(const Graph& _graph, const LengthMap& _length) :
00433 graph(&_graph), length(&_length),
00434 _pred(0), local_pred(false),
00435 _dist(0), local_dist(false),
00436 _heap_cross_ref(0), local_heap_cross_ref(false),
00437 _heap(0), local_heap(false) {}
00438
00440 ~Johnson() {
00441 if (local_pred) delete _pred;
00442 if (local_dist) delete _dist;
00443 if (local_heap_cross_ref) delete _heap_cross_ref;
00444 if (local_heap) delete _heap;
00445 }
00446
00451 Johnson &lengthMap(const LengthMap &m) {
00452 length = &m;
00453 return *this;
00454 }
00455
00463 Johnson &predMap(PredMap &m) {
00464 if(local_pred) {
00465 delete _pred;
00466 local_pred=false;
00467 }
00468 _pred = &m;
00469 return *this;
00470 }
00471
00479 Johnson &distMap(DistMap &m) {
00480 if(local_dist) {
00481 delete _dist;
00482 local_dist=false;
00483 }
00484 _dist = &m;
00485 return *this;
00486 }
00487
00488 public:
00489
00497
00499
00503 void init() {
00504 create_maps();
00505 }
00506
00519 template <typename PotentialMap>
00520 void shiftedStart(const PotentialMap& potential) {
00521 typename Graph::template EdgeMap<Value> shiftlen(*graph);
00522 for (EdgeIt it(*graph); it != INVALID; ++it) {
00523 shiftlen[it] = (*length)[it]
00524 + potential[graph->source(it)]
00525 - potential[graph->target(it)];
00526 }
00527
00528 typename Dijkstra<Graph, typename Graph::template EdgeMap<Value> >::
00529 template DefHeap<Heap, HeapCrossRef>::
00530 Create dijkstra(*graph, shiftlen);
00531
00532 dijkstra.heap(*_heap, *_heap_cross_ref);
00533
00534 for (NodeIt it(*graph); it != INVALID; ++it) {
00535 dijkstra.run(it);
00536 for (NodeIt jt(*graph); jt != INVALID; ++jt) {
00537 if (dijkstra.reached(jt)) {
00538 _dist->set(it, jt, dijkstra.dist(jt) +
00539 potential[jt] - potential[it]);
00540 _pred->set(it, jt, dijkstra.predEdge(jt));
00541 } else {
00542 _dist->set(it, jt, OperationTraits::infinity());
00543 _pred->set(it, jt, INVALID);
00544 }
00545 }
00546 }
00547 }
00548
00556 void start() {
00557
00558 typedef typename BellmanFord<Graph, LengthMap>::
00559 template DefOperationTraits<OperationTraits>::
00560 template DefPredMap<NullMap<Node, Edge> >::
00561 Create BellmanFordType;
00562
00563 BellmanFordType bellmanford(*graph, *length);
00564
00565 NullMap<Node, Edge> predMap;
00566
00567 bellmanford.predMap(predMap);
00568
00569 bellmanford.init(OperationTraits::zero());
00570 bellmanford.start();
00571
00572 shiftedStart(bellmanford.distMap());
00573 }
00574
00583 bool checkedStart() {
00584
00585 typedef typename BellmanFord<Graph, LengthMap>::
00586 template DefOperationTraits<OperationTraits>::
00587 template DefPredMap<NullMap<Node, Edge> >::
00588 Create BellmanFordType;
00589
00590 BellmanFordType bellmanford(*graph, *length);
00591
00592 NullMap<Node, Edge> predMap;
00593
00594 bellmanford.predMap(predMap);
00595
00596 bellmanford.init(OperationTraits::zero());
00597 if (!bellmanford.checkedStart()) return false;
00598
00599 shiftedStart(bellmanford.distMap());
00600 return true;
00601 }
00602
00603
00617 void run() {
00618 init();
00619 start();
00620 }
00621
00623
00629
00631
00640 template <typename Path>
00641 bool getPath(Path &p, Node source, Node target) {
00642 if (connected(source, target)) {
00643 p.clear();
00644 typename Path::Builder b(target);
00645 for(b.setStartNode(target); predEdge(source, target) != INVALID;
00646 target = predNode(target)) {
00647 b.pushFront(predEdge(source, target));
00648 }
00649 b.commit();
00650 return true;
00651 }
00652 return false;
00653 }
00654
00661 Value dist(Node source, Node target) const {
00662 return (*_dist)(source, target);
00663 }
00664
00674 Edge predEdge(Node root, Node node) const {
00675 return (*_pred)(root, node);
00676 }
00677
00687 Node predNode(Node root, Node node) const {
00688 return (*_pred)(root, node) == INVALID ?
00689 INVALID : graph->source((*_pred)(root, node));
00690 }
00691
00697 const DistMap &distMap() const { return *_dist;}
00698
00704 const PredMap &predMap() const { return *_pred;}
00705
00711 bool connected(Node source, Node target) {
00712 return (*_dist)(source, target) != OperationTraits::infinity();
00713 }
00714
00716 };
00717
00718 }
00719
00720 #endif