johnson.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_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     // The type of the length of the edges.
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 } //END OF NAMESPACE LEMON
00719 
00720 #endif

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