dag_shortest_path.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_DAG_SHORTEST_PATH_H
00020 #define LEMON_DAG_SHORTEST_PATH_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 #include <lemon/topology.h>
00032 
00033 #include <limits>
00034 
00035 namespace lemon {
00036 
00044   template <
00045     typename Value, 
00046     bool has_infinity = std::numeric_limits<Value>::has_infinity>
00047   struct DagShortestPathDefaultOperationTraits {
00049     static Value zero() {
00050       return static_cast<Value>(0);
00051     }
00053     static Value infinity() {
00054       return std::numeric_limits<Value>::infinity();
00055     }
00057     static Value plus(const Value& left, const Value& right) {
00058       return left + right;
00059     }
00061     static bool less(const Value& left, const Value& right) {
00062       return left < right;
00063     }
00064   };
00065 
00066   template <typename Value>
00067   struct DagShortestPathDefaultOperationTraits<Value, false> {
00068     static Value zero() {
00069       return static_cast<Value>(0);
00070     }
00071     static Value infinity() {
00072       return std::numeric_limits<Value>::max();
00073     }
00074     static Value plus(const Value& left, const Value& right) {
00075       if (left == infinity() || right == infinity()) return infinity();
00076       return left + right;
00077     }
00078     static bool less(const Value& left, const Value& right) {
00079       return left < right;
00080     }
00081   };
00082   
00088   template<class _Graph, class _LengthMap>
00089   struct DagShortestPathDefaultTraits {
00091     typedef _Graph Graph;
00092 
00097     typedef _LengthMap LengthMap;
00098 
00099     // The type of the length of the edges.
00100     typedef typename _LengthMap::Value Value;
00101 
00107     typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
00108  
00116     typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
00117 
00124     static PredMap *createPredMap(const _Graph& graph) {
00125       return new PredMap(graph);
00126     }
00127 
00133     typedef typename Graph::template NodeMap<typename _LengthMap::Value> 
00134     DistMap;
00135 
00141     static DistMap *createDistMap(const _Graph& graph) {
00142       return new DistMap(graph);
00143     }
00144 
00145   };
00146   
00156   template <
00157     typename Value, 
00158     bool has_infinity = std::numeric_limits<Value>::has_infinity>
00159   struct DagLongestPathOperationTraits {
00161     static Value zero() {
00162       return static_cast<Value>(0);
00163     }
00165     static Value infinity() {
00166       return -(std::numeric_limits<Value>::infinity());
00167     }
00169     static Value plus(const Value& left, const Value& right) {
00170       return left + right;
00171     }
00173     static bool less(const Value& left, const Value& right) {
00174       return left > right;
00175     }
00176   };
00177 
00178   template <typename Value>
00179   struct DagLongestPathOperationTraits<Value, false> {
00180     static Value zero() {
00181       return static_cast<Value>(0);
00182     }
00183     static Value infinity() {
00184       return std::numeric_limits<Value>::min();
00185     }
00186     static Value plus(const Value& left, const Value& right) {
00187       if (left == infinity() || right == infinity()) return infinity();
00188       return left + right;
00189     }
00190     static bool less(const Value& left, const Value& right) {
00191       return left > right;
00192     }
00193   };
00194 
00200   template<class _Graph, class _LengthMap>
00201   struct DagLongestPathTraits {
00203     typedef _Graph Graph;
00204 
00209     typedef _LengthMap LengthMap;
00210 
00211     // The type of the length of the edges.
00212     typedef typename _LengthMap::Value Value;
00213 
00219     typedef DagLongestPathOperationTraits<Value> OperationTraits;
00220  
00228     typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
00229 
00236     static PredMap *createPredMap(const _Graph& graph) {
00237       return new PredMap(graph);
00238     }
00239 
00245     typedef typename Graph::template NodeMap<typename _LengthMap::Value> 
00246     DistMap;
00247 
00253     static DistMap *createDistMap(const _Graph& graph) {
00254       return new DistMap(graph);
00255     }
00256 
00257   };
00258   
00259 
00287 
00288 #ifdef DOXYGEN
00289   template <typename _Graph, typename _LengthMap, typename _Traits>
00290 #else
00291   template <typename _Graph=ListGraph,
00292             typename _LengthMap=typename _Graph::template EdgeMap<int>,
00293             typename _Traits=DagShortestPathDefaultTraits<_Graph,_LengthMap> >
00294 #endif
00295   class DagShortestPath {
00296   public:
00297     
00302 
00303     class UninitializedParameter : public lemon::UninitializedParameter {
00304     public:
00305       virtual const char* exceptionName() const {
00306         return "lemon::DagShortestPath::UninitializedParameter";
00307       }
00308     };
00309 
00310     typedef _Traits Traits;
00312     typedef typename _Traits::Graph Graph;
00313 
00314     typedef typename Graph::Node Node;
00315     typedef typename Graph::NodeIt NodeIt;
00316     typedef typename Graph::Edge Edge;
00317     typedef typename Graph::EdgeIt EdgeIt;
00318     typedef typename Graph::OutEdgeIt OutEdgeIt;
00319     
00321     typedef typename _Traits::LengthMap::Value Value;
00323     typedef typename _Traits::LengthMap LengthMap;
00326     typedef typename _Traits::PredMap PredMap;
00328     typedef typename _Traits::DistMap DistMap;
00330     typedef typename _Traits::OperationTraits OperationTraits;
00332     typedef typename Graph::NodeMap<Value> WeightMap;
00333   private:
00335     const Graph *graph;
00337     const LengthMap *length;
00339     PredMap *_pred;
00341     bool local_pred;
00343     DistMap *_dist;
00345     bool local_dist;
00347     unsigned int _process_step;
00348 
00349     std::vector<Node> _node_order;
00350 
00352     void create_maps() {
00353       if(!_pred) {
00354         local_pred = true;
00355         _pred = Traits::createPredMap(*graph);
00356       }
00357       if(!_dist) {
00358         local_dist = true;
00359         _dist = Traits::createDistMap(*graph);
00360       }
00361     }
00362     
00363   public :
00364  
00365     typedef DagShortestPath Create;
00366 
00368 
00370 
00371     template <class T>
00372     struct DefPredMapTraits : public Traits {
00373       typedef T PredMap;
00374       static PredMap *createPredMap(const Graph&) {
00375         throw UninitializedParameter();
00376       }
00377     };
00378 
00383     template <class T>
00384     struct DefPredMap {
00385       typedef DagShortestPath< Graph, LengthMap, DefPredMapTraits<T> > Create;
00386     };
00387     
00388     template <class T>
00389     struct DefDistMapTraits : public Traits {
00390       typedef T DistMap;
00391       static DistMap *createDistMap(const Graph& graph) {
00392         throw UninitializedParameter();
00393       }
00394     };
00395 
00401     template <class T>
00402     struct DefDistMap 
00403       : public DagShortestPath< Graph, LengthMap, DefDistMapTraits<T> > {
00404       typedef DagShortestPath< Graph, LengthMap, DefDistMapTraits<T> > Create;
00405     };
00406     
00407     template <class T>
00408     struct DefOperationTraitsTraits : public Traits {
00409       typedef T OperationTraits;
00410     };
00411     
00417     template <class T>
00418     struct DefOperationTraits
00419       : public DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits<T> > {
00420       typedef DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits<T> >
00421       Create;
00422     };
00423     
00425 
00426   protected:
00427     
00428     DagShortestPath() {}
00429 
00430   public:      
00431     
00436     DagShortestPath(const Graph& _graph, const LengthMap& _length) :
00437       graph(&_graph), length(&_length),
00438       _pred(0), local_pred(false),
00439       _dist(0), local_dist(false){}
00440 
00447     DagShortestPath(const Graph& _graph, const WeightMap& _length) :
00448       graph(&_graph),
00449       _pred(0), local_pred(false),
00450       _dist(0), local_dist(false){
00451       length=new LengthMap(_graph);
00452       _dist=new DistMap(_graph);
00453       for(EdgeIt eit(_graph);eit!=INVALID;++eit)
00454         (const_cast<LengthMap*>(length))->set(eit,_length[_graph.target(eit)]);
00455       }
00456 
00458     ~DagShortestPath() {
00459       if(local_pred) delete _pred;
00460       if(local_dist) delete _dist;
00461     }
00462 
00467     DagShortestPath &lengthMap(const LengthMap &m) {
00468       length = &m;
00469       return *this;
00470     }
00471 
00479     DagShortestPath &predMap(PredMap &m) {
00480       if(local_pred) {
00481         delete _pred;
00482         local_pred=false;
00483       }
00484       _pred = &m;
00485       return *this;
00486     }
00487 
00495     DagShortestPath &distMap(DistMap &m) {
00496       if(local_dist) {
00497         delete _dist;
00498         local_dist=false;
00499       }
00500       _dist = &m;
00501       return *this;
00502     }
00503 
00515 
00517 
00521     void init(const Value value = OperationTraits::infinity()) {
00522       typedef typename Graph::template NodeMap<int> NodeOrderMap;
00523       _process_step=0;
00524       NodeOrderMap node_order(*graph);
00525       topologicalSort(*graph,node_order);
00526       _node_order.resize(countNodes(*graph),INVALID);
00527       create_maps();
00528       for (NodeIt it(*graph); it != INVALID; ++it) {
00529         _node_order[node_order[it]]=it;
00530         _pred->set(it, INVALID);
00531         _dist->set(it, value);
00532       }
00533     }
00534 
00540     void init(const typename Graph::template NodeMap<int>& node_order,
00541          const Value value = OperationTraits::infinity()) {
00542       _process_step=0;
00543       _node_order.resize(countNodes(*graph),INVALID);
00544       create_maps();
00545       for (NodeIt it(*graph); it != INVALID; ++it) {
00546         _node_order[node_order[it]]=it;
00547         _pred->set(it, INVALID);
00548         _dist->set(it, value);
00549       }
00550     }
00551 
00557     void init(const std::vector<Node>& node_order,
00558         const Value value = OperationTraits::infinity()) {
00559       _process_step=0;
00560       _node_order=node_order;
00561       create_maps();
00562       for (NodeIt it(*graph); it != INVALID; ++it) {
00563         _pred->set(it, INVALID);
00564         _dist->set(it, value);
00565       }
00566     }
00567 
00572     bool checkedInit(const Value value = OperationTraits::infinity()) {
00573       typedef typename Graph::template NodeMap<int> NodeOrderMap;
00574       NodeOrderMap node_order(*graph);
00575       if(!checkedTopologicalSort(*graph,node_order))return false;
00576       init(node_order,value);
00577       return true;
00578     }
00579 
00586     bool checkedInit(const typename Graph::template NodeMap<int>& node_order, 
00587                      const Value value = OperationTraits::infinity()) {
00588       for(NodeIt it(*graph);it!=INVALID;++it){
00589         for(OutEdgeIt oeit(*graph,it);oeit!=INVALID;++oeit){
00590           if(node_order[graph->target(oeit)]<node_order[it])return false;
00591         }
00592       }
00593       init(node_order,value);
00594       return true;
00595     }
00596 
00603     bool checkedInit(const std::vector<Node>& node_order, 
00604                      const Value value = OperationTraits::infinity()) {
00605       typedef typename Graph::template NodeMap<bool> BoolNodeMap;
00606       BoolNodeMap _processed(*graph,false);
00607       for(unsigned int i=0;i<_node_order.size();++i){
00608         _processed[node_order[i]]=true;
00609         for(OutEdgeIt oeit(*graph,node_order[i]);oeit!=INVALID;++oeit){
00610           if(_processed[graph->target(oeit)])return false;
00611         }
00612       }
00613       init(node_order,value);
00614       return true;
00615     }
00616 
00621     void addSource(Node source, Value dst = OperationTraits::zero()) {
00622       if((*_dist)[source] != dst){
00623         _dist->set(source, dst);
00624       }
00625     }
00626 
00635     Node processNextNode() {
00636       if(reached(_node_order[_process_step])){
00637         for (OutEdgeIt it(*graph, _node_order[_process_step]); it != INVALID; ++it) {
00638           Node target = graph->target(it);
00639           Value relaxed =
00640             OperationTraits::plus((*_dist)[_node_order[_process_step]], (*length)[it]);
00641           if (OperationTraits::less(relaxed, (*_dist)[target])) {
00642             _pred->set(target, it);
00643             _dist->set(target, relaxed);
00644           }
00645         }
00646       }
00647       ++_process_step;
00648       return _node_order[_process_step-1];
00649     }
00650 
00656     bool emptyQueue() { return _node_order.size()-1==_process_step; }
00657 
00661     int queueSize() { return _node_order.size()-1-_process_step; }
00662 
00673     void start() {
00674       while(!emptyQueue()) {
00675         processNextNode();
00676       }
00677     }
00678 
00693     void run(Node s) {
00694       init();
00695       addSource(s);
00696       start();
00697     }
00698     
00708     bool checkedRun(Node s) {
00709       if(!checkedInit())return false;
00710       addSource(s);
00711       start();
00712       return true;
00713     }
00714     
00716 
00722     
00724 
00734     template <typename Path>
00735     bool getPath(Path &p, Node t) {
00736       if(reached(t)) {
00737         p.clear();
00738         typename Path::Builder b(p);
00739         for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
00740           b.pushFront(predEdge(t));
00741         b.commit();
00742         return true;
00743       }
00744       return false;
00745     }
00746           
00753     Value dist(Node v) const { return (*_dist)[v]; }
00754 
00764     Edge predEdge(Node v) const { return (*_pred)[v]; }
00765 
00774     Node predNode(Node v) const { 
00775       return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]); 
00776     }
00777     
00782     const DistMap &distMap() const { return *_dist;}
00783  
00789     const PredMap &predMap() const { return *_pred; }
00790  
00796     bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
00797     
00799   };
00800  
00806   template <typename _Graph, typename _LengthMap>
00807   struct DagShortestPathWizardDefaultTraits {
00809     typedef _Graph Graph;
00810 
00815     typedef _LengthMap LengthMap;
00816 
00818     typedef typename _LengthMap::Value Value;
00819 
00825     typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
00826 
00833     typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
00834 
00838     static PredMap *createPredMap(const _Graph &) {
00839       return new PredMap();
00840     }
00845     typedef NullMap<typename Graph::Node, Value> DistMap;
00849     static DistMap *createDistMap(const _Graph &) {
00850       return new DistMap();
00851     }
00852   };
00853   
00863   template<class _Graph,class _LengthMap>
00864   class DagShortestPathWizardBase 
00865     : public DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> {
00866 
00867     typedef DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> Base;
00868   protected:
00870     typedef typename Base::Graph::Node Node;
00871 
00873     void *_graph;
00875     void *_length;
00877     void *_pred;
00879     void *_dist;
00881     Node _source;
00882 
00883     public:
00885     
00888     DagShortestPathWizardBase() : _graph(0), _length(0), _pred(0),
00889                            _dist(0), _source(INVALID) {}
00890 
00892     
00899     DagShortestPathWizardBase(const _Graph& graph, 
00900                           const _LengthMap& length, 
00901                           Node source = INVALID) :
00902       _graph((void *)&graph), _length((void *)&length), _pred(0),
00903       _dist(0), _source(source) {}
00904 
00905   };
00906   
00908 
00926   template<class _Traits>
00927   class DagShortestPathWizard : public _Traits {
00928     typedef _Traits Base;
00929 
00931     typedef typename _Traits::Graph Graph;
00932 
00933     typedef typename Graph::Node Node;
00934     typedef typename Graph::NodeIt NodeIt;
00935     typedef typename Graph::Edge Edge;
00936     typedef typename Graph::OutEdgeIt EdgeIt;
00937     
00939     typedef typename _Traits::LengthMap LengthMap;
00940 
00942     typedef typename LengthMap::Value Value;
00943 
00946     typedef typename _Traits::PredMap PredMap;
00947 
00949     typedef typename _Traits::DistMap DistMap;
00950 
00951   public:
00953     DagShortestPathWizard() : _Traits() {}
00954 
00959     DagShortestPathWizard(const Graph& graph, const LengthMap& length, 
00960                       Node source = INVALID) 
00961       : _Traits(graph, length, source) {}
00962 
00964     DagShortestPathWizard(const _Traits &b) : _Traits(b) {}
00965 
00966     ~DagShortestPathWizard() {}
00967 
00972     void run() {
00973       if(Base::_source == INVALID) throw UninitializedParameter();
00974       DagShortestPath<Graph,LengthMap,_Traits> 
00975         bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
00976       if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
00977       if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
00978       bf.run(Base::_source);
00979     }
00980 
00985     void run(Node source) {
00986       Base::_source = source;
00987       run();
00988     }
00989 
00990     template<class T>
00991     struct DefPredMapBase : public Base {
00992       typedef T PredMap;
00993       static PredMap *createPredMap(const Graph &) { return 0; };
00994       DefPredMapBase(const _Traits &b) : _Traits(b) {}
00995     };
00996     
01003     template<class T>
01004     DagShortestPathWizard<DefPredMapBase<T> > predMap(const T &t) 
01005     {
01006       Base::_pred=(void *)&t;
01007       return DagShortestPathWizard<DefPredMapBase<T> >(*this);
01008     }
01009     
01010     template<class T>
01011     struct DefDistMapBase : public Base {
01012       typedef T DistMap;
01013       static DistMap *createDistMap(const Graph &) { return 0; };
01014       DefDistMapBase(const _Traits &b) : _Traits(b) {}
01015     };
01016     
01023     template<class T>
01024     DagShortestPathWizard<DefDistMapBase<T> > distMap(const T &t) {
01025       Base::_dist=(void *)&t;
01026       return DagShortestPathWizard<DefDistMapBase<T> >(*this);
01027     }
01028 
01029     template<class T>
01030     struct DefOperationTraitsBase : public Base {
01031       typedef T OperationTraits;
01032       DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
01033     };
01034     
01041     template<class T>
01042     DagShortestPathWizard<DefOperationTraitsBase<T> > distMap() {
01043       return DagShortestPathWizard<DefDistMapBase<T> >(*this);
01044     }
01045     
01050     DagShortestPathWizard<_Traits>& source(Node source) {
01051       Base::_source = source;
01052       return *this;
01053     }
01054     
01055   };
01056   
01074   template<class _Graph, class _LengthMap>
01075   DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
01076   dagShortestPath(const _Graph& graph,
01077               const _LengthMap& length, 
01078               typename _Graph::Node source = INVALID) {
01079     return DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
01080       (graph, length, source);
01081   }
01082 
01083 } //END OF NAMESPACE LEMON
01084 
01085 #endif
01086 

Generated on Fri Feb 3 18:36:11 2006 for LEMON by  doxygen 1.4.6