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