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