floyd_warshall.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_FLOYD_WARSHALL_H
00020 #define LEMON_FLOYD_WARSHALL_H
00021 
00026 
00027 #include <lemon/list_graph.h>
00028 #include <lemon/graph_utils.h>
00029 #include <lemon/invalid.h>
00030 #include <lemon/error.h>
00031 #include <lemon/matrix_maps.h>
00032 #include <lemon/maps.h>
00033 
00034 #include <limits>
00035 
00036 namespace lemon {
00037 
00045   template <
00046     typename Value, 
00047     bool has_infinity = std::numeric_limits<Value>::has_infinity>
00048   struct FloydWarshallDefaultOperationTraits {
00050     static Value zero() {
00051       return static_cast<Value>(0);
00052     }
00054     static Value infinity() {
00055       return std::numeric_limits<Value>::infinity();
00056     }
00058     static Value plus(const Value& left, const Value& right) {
00059       return left + right;
00060     }
00062     static bool less(const Value& left, const Value& right) {
00063       return left < right;
00064     }
00065   };
00066 
00067   template <typename Value>
00068   struct FloydWarshallDefaultOperationTraits<Value, false> {
00069     static Value zero() {
00070       return static_cast<Value>(0);
00071     }
00072     static Value infinity() {
00073       return std::numeric_limits<Value>::max();
00074     }
00075     static Value plus(const Value& left, const Value& right) {
00076       if (left == infinity() || right == infinity()) return infinity();
00077       return left + right;
00078     }
00079     static bool less(const Value& left, const Value& right) {
00080       return left < right;
00081     }
00082   };
00083   
00089   template<class _Graph, class _LengthMap>
00090   struct FloydWarshallDefaultTraits {
00092     typedef _Graph Graph;
00093 
00098     typedef _LengthMap LengthMap;
00099 
00100     // The type of the length of the edges.
00101     typedef typename _LengthMap::Value Value;
00102 
00108     typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits;
00109  
00116     typedef DynamicMatrixMap<Graph, typename Graph::Node, 
00117                              typename Graph::Edge> PredMap;
00118 
00125     static PredMap *createPredMap(const _Graph& graph) {
00126       return new PredMap(graph);
00127     }
00128 
00134     typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
00135 
00141     static DistMap *createDistMap(const _Graph& graph) {
00142       return new DistMap(graph);
00143     }
00144 
00145   };
00146   
00184 
00185 #ifdef DOXYGEN
00186   template <typename _Graph, typename _LengthMap typename _Traits >
00187 #else
00188   template <typename _Graph=ListGraph,
00189             typename _LengthMap=typename _Graph::template EdgeMap<int>,
00190             typename _Traits=FloydWarshallDefaultTraits<_Graph,_LengthMap> >
00191 #endif
00192   class FloydWarshall {
00193   public:
00194     
00199 
00200     class UninitializedParameter : public lemon::UninitializedParameter {
00201     public:
00202       virtual const char* exceptionName() const {
00203         return "lemon::FloydWarshall::UninitializedParameter";
00204       }
00205     };
00206 
00207     typedef _Traits Traits;
00209     typedef typename _Traits::Graph Graph;
00210 
00211     typedef typename Graph::Node Node;
00212     typedef typename Graph::NodeIt NodeIt;
00213     typedef typename Graph::Edge Edge;
00214     typedef typename Graph::EdgeIt EdgeIt;
00215     
00217     typedef typename _Traits::LengthMap::Value Value;
00219     typedef typename _Traits::LengthMap LengthMap;
00223     typedef typename _Traits::PredMap PredMap;
00226     typedef typename _Traits::DistMap DistMap;
00228     typedef typename _Traits::OperationTraits OperationTraits;
00229   private:
00231     const Graph *graph;
00233     const LengthMap *length;
00235     PredMap *_pred;
00237     bool local_pred;
00239     DistMap *_dist;
00241     bool local_dist;
00242 
00244     void create_maps() {
00245       if(!_pred) {
00246         local_pred = true;
00247         _pred = Traits::createPredMap(*graph);
00248       }
00249       if(!_dist) {
00250         local_dist = true;
00251         _dist = Traits::createDistMap(*graph);
00252       }
00253     }
00254     
00255   public :
00256  
00258 
00260 
00261     template <class T>
00262     struct DefPredMapTraits : public Traits {
00263       typedef T PredMap;
00264       static PredMap *createPredMap(const Graph& graph) {
00265         throw UninitializedParameter();
00266       }
00267     };
00268 
00273     template <class T>
00274     struct DefPredMap 
00275       : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {
00276       typedef FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > Create;
00277     };
00278     
00279     template <class T>
00280     struct DefDistMapTraits : public Traits {
00281       typedef T DistMap;
00282       static DistMap *createDistMap(const Graph& graph) {
00283         throw UninitializedParameter();
00284       }
00285     };
00291     template <class T>
00292     struct DefDistMap 
00293       : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {
00294       typedef FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > Create;
00295     };
00296     
00297     template <class T>
00298     struct DefOperationTraitsTraits : public Traits {
00299       typedef T OperationTraits;
00300     };
00301     
00306     template <class T>
00307     struct DefOperationTraits
00308       : public FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> > {
00309       typedef FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> >
00310       Create;
00311     };
00312     
00314 
00315   protected:
00316 
00317     FloydWarshall() {}
00318 
00319   public:      
00320 
00321     typedef FloydWarshall Create;
00322     
00327     FloydWarshall(const Graph& _graph, const LengthMap& _length) :
00328       graph(&_graph), length(&_length),
00329       _pred(0), local_pred(false),
00330       _dist(0), local_dist(false) {}
00331     
00333     ~FloydWarshall() {
00334       if(local_pred) delete _pred;
00335       if(local_dist) delete _dist;
00336     }
00337 
00342     FloydWarshall &lengthMap(const LengthMap &m) {
00343       length = &m;
00344       return *this;
00345     }
00346 
00354     FloydWarshall &predMap(PredMap &m) {
00355       if(local_pred) {
00356         delete _pred;
00357         local_pred=false;
00358       }
00359       _pred = &m;
00360       return *this;
00361     }
00362 
00370     FloydWarshall &distMap(DistMap &m) {
00371       if(local_dist) {
00372         delete _dist;
00373         local_dist=false;
00374       }
00375       _dist = &m;
00376       return *this;
00377     }
00378 
00386 
00388 
00392     void init() {
00393       create_maps();
00394       for (NodeIt it(*graph); it != INVALID; ++it) {
00395         for (NodeIt jt(*graph); jt != INVALID; ++jt) {
00396           _pred->set(it, jt, INVALID);
00397           _dist->set(it, jt, OperationTraits::infinity());
00398         }
00399         _dist->set(it, it, OperationTraits::zero());
00400       }
00401       for (EdgeIt it(*graph); it != INVALID; ++it) {
00402         Node source = graph->source(it);
00403         Node target = graph->target(it);        
00404         if (OperationTraits::less((*length)[it], (*_dist)(source, target))) {
00405           _dist->set(source, target, (*length)[it]);
00406           _pred->set(source, target, it);
00407         }
00408       }
00409     }
00410     
00418     void start() {
00419       for (NodeIt kt(*graph); kt != INVALID; ++kt) {
00420         for (NodeIt it(*graph); it != INVALID; ++it) {
00421           for (NodeIt jt(*graph); jt != INVALID; ++jt) {
00422             Value relaxed = OperationTraits::plus((*_dist)(it, kt),
00423                                                   (*_dist)(kt, jt));
00424             if (OperationTraits::less(relaxed, (*_dist)(it, jt))) {
00425               _dist->set(it, jt, relaxed);
00426               _pred->set(it, jt, (*_pred)(kt, jt));
00427             }
00428           }
00429         }
00430       }
00431     }
00432 
00441     bool checkedStart() {
00442       start();
00443       for (NodeIt it(*graph); it != INVALID; ++it) {
00444         if (OperationTraits::less((*dist)(it, it), OperationTraits::zero())) {
00445           return false;
00446         }
00447       }
00448       return true;
00449     }
00450     
00464     void run() {
00465       init();
00466       start();
00467     }
00468     
00470 
00476     
00478 
00487     template <typename Path>
00488     bool getPath(Path &p, Node source, Node target) {
00489       if (connected(source, target)) {
00490         p.clear();
00491         typename Path::Builder b(target);
00492         for(b.setStartNode(target); predEdge(source, target) != INVALID;
00493             target = predNode(target)) {
00494           b.pushFront(predEdge(source, target));
00495         }
00496         b.commit();
00497         return true;
00498       }
00499       return false;
00500     }
00501           
00508     Value dist(Node source, Node target) const { 
00509       return (*_dist)(source, target); 
00510     }
00511 
00521     Edge predEdge(Node root, Node node) const { 
00522       return (*_pred)(root, node); 
00523     }
00524 
00534     Node predNode(Node root, Node node) const { 
00535       return (*_pred)(root, node) == INVALID ? 
00536       INVALID : graph->source((*_pred)(root, node)); 
00537     }
00538     
00544     const DistMap &distMap() const { return *_dist;}
00545  
00551     const PredMap &predMap() const { return *_pred;}
00552  
00558     bool connected(Node source, Node target) { 
00559       return (*_dist)(source, target) != OperationTraits::infinity(); 
00560     }
00561     
00563   };
00564  
00565 } //END OF NAMESPACE LEMON
00566 
00567 #endif
00568 

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