1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/dijkstra.h Sun Feb 06 20:14:30 2005 +0000
1.3 @@ -0,0 +1,915 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_DIJKSTRA_H
1.21 +#define LEMON_DIJKSTRA_H
1.22 +
1.23 +///\ingroup flowalgs
1.24 +///\file
1.25 +///\brief Dijkstra algorithm.
1.26 +
1.27 +#include <lemon/list_graph.h>
1.28 +#include <lemon/bin_heap.h>
1.29 +#include <lemon/invalid.h>
1.30 +#include <lemon/error.h>
1.31 +#include <lemon/maps.h>
1.32 +
1.33 +namespace lemon {
1.34 +
1.35 +
1.36 +/// \addtogroup flowalgs
1.37 +/// @{
1.38 +
1.39 + ///Default traits class of Dijkstra class.
1.40 +
1.41 + ///Default traits class of Dijkstra class.
1.42 + ///\param GR Graph type.
1.43 + ///\param LM Type of length map.
1.44 + template<class GR, class LM>
1.45 + struct DijkstraDefaultTraits
1.46 + {
1.47 + ///The graph type the algorithm runs on.
1.48 + typedef GR Graph;
1.49 + ///The type of the map that stores the edge lengths.
1.50 +
1.51 + ///The type of the map that stores the edge lengths.
1.52 + ///It must meet the \ref concept::ReadMap "ReadMap" concept.
1.53 + typedef LM LengthMap;
1.54 + //The type of the length of the edges.
1.55 + typedef typename LM::Value Value;
1.56 + ///The heap type used by Dijkstra algorithm.
1.57 +
1.58 + ///The heap type used by Dijkstra algorithm.
1.59 + ///
1.60 + ///\sa BinHeap
1.61 + ///\sa Dijkstra
1.62 + typedef BinHeap<typename Graph::Node,
1.63 + typename LM::Value,
1.64 + typename GR::template NodeMap<int>,
1.65 + std::less<Value> > Heap;
1.66 +
1.67 + ///\brief The type of the map that stores the last
1.68 + ///edges of the shortest paths.
1.69 + ///
1.70 + ///The type of the map that stores the last
1.71 + ///edges of the shortest paths.
1.72 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.73 + ///
1.74 + typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
1.75 + ///Instantiates a PredMap.
1.76 +
1.77 + ///This function instantiates a \ref PredMap.
1.78 + ///\param G is the graph, to which we would like to define the PredMap.
1.79 + ///\todo The graph alone may be insufficient for the initialization
1.80 + static PredMap *createPredMap(const GR &G)
1.81 + {
1.82 + return new PredMap(G);
1.83 + }
1.84 + ///\brief The type of the map that stores the last but one
1.85 + ///nodes of the shortest paths.
1.86 + ///
1.87 + ///The type of the map that stores the last but one
1.88 + ///nodes of the shortest paths.
1.89 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.90 + ///
1.91 + typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.92 + ///Instantiates a PredNodeMap.
1.93 +
1.94 + ///This function instantiates a \ref PredNodeMap.
1.95 + ///\param G is the graph, to which we would like to define the \ref PredNodeMap
1.96 + static PredNodeMap *createPredNodeMap(const GR &G)
1.97 + {
1.98 + return new PredNodeMap();
1.99 + }
1.100 +
1.101 + ///The type of the map that stores whether a nodes is reached.
1.102 +
1.103 + ///The type of the map that stores whether a nodes is reached.
1.104 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.105 + ///By default it is a NullMap.
1.106 + ///\todo If it is set to a real map, Dijkstra::reached() should read this.
1.107 + ///\todo named parameter to set this type, function to read and write.
1.108 + typedef NullMap<typename Graph::Node,bool> ReachedMap;
1.109 + ///Instantiates a ReachedMap.
1.110 +
1.111 + ///This function instantiates a \ref ReachedMap.
1.112 + ///\param G is the graph, to which we would like to define the \ref ReachedMap
1.113 + static ReachedMap *createReachedMap(const GR &G)
1.114 + {
1.115 + return new ReachedMap();
1.116 + }
1.117 + ///The type of the map that stores the dists of the nodes.
1.118 +
1.119 + ///The type of the map that stores the dists of the nodes.
1.120 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.121 + ///
1.122 + typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
1.123 + ///Instantiates a DistMap.
1.124 +
1.125 + ///This function instantiates a \ref DistMap.
1.126 + ///\param G is the graph, to which we would like to define the \ref DistMap
1.127 + static DistMap *createDistMap(const GR &G)
1.128 + {
1.129 + return new DistMap(G);
1.130 + }
1.131 + };
1.132 +
1.133 + ///%Dijkstra algorithm class.
1.134 +
1.135 + ///This class provides an efficient implementation of %Dijkstra algorithm.
1.136 + ///The edge lengths are passed to the algorithm using a
1.137 + ///\ref concept::ReadMap "ReadMap",
1.138 + ///so it is easy to change it to any kind of length.
1.139 + ///
1.140 + ///The type of the length is determined by the
1.141 + ///\ref concept::ReadMap::Value "Value" of the length map.
1.142 + ///
1.143 + ///It is also possible to change the underlying priority heap.
1.144 + ///
1.145 + ///\param GR The graph type the algorithm runs on. The default value is
1.146 + ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
1.147 + ///is only passed to \ref DijkstraDefaultTraits.
1.148 + ///\param LM This read-only
1.149 + ///EdgeMap
1.150 + ///determines the
1.151 + ///lengths of the edges. It is read once for each edge, so the map
1.152 + ///may involve in relatively time consuming process to compute the edge
1.153 + ///length if it is necessary. The default map type is
1.154 + ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
1.155 + ///The value of LM is not used directly by Dijkstra, it
1.156 + ///is only passed to \ref DijkstraDefaultTraits.
1.157 + ///\param TR Traits class to set various data types used by the algorithm.
1.158 + ///The default traits class is
1.159 + ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
1.160 + ///See \ref DijkstraDefaultTraits for the documentation of
1.161 + ///a Dijkstra traits class.
1.162 + ///
1.163 + ///\author Jacint Szabo and Alpar Juttner
1.164 + ///\todo A compare object would be nice.
1.165 +
1.166 +#ifdef DOXYGEN
1.167 + template <typename GR,
1.168 + typename LM,
1.169 + typename TR>
1.170 +#else
1.171 + template <typename GR=ListGraph,
1.172 + typename LM=typename GR::template EdgeMap<int>,
1.173 + typename TR=DijkstraDefaultTraits<GR,LM> >
1.174 +#endif
1.175 + class Dijkstra {
1.176 + public:
1.177 + /**
1.178 + * \brief \ref Exception for uninitialized parameters.
1.179 + *
1.180 + * This error represents problems in the initialization
1.181 + * of the parameters of the algorithms.
1.182 + */
1.183 + class UninitializedParameter : public lemon::UninitializedParameter {
1.184 + public:
1.185 + virtual const char* exceptionName() const {
1.186 + return "lemon::Dijsktra::UninitializedParameter";
1.187 + }
1.188 + };
1.189 +
1.190 + typedef TR Traits;
1.191 + ///The type of the underlying graph.
1.192 + typedef typename TR::Graph Graph;
1.193 + ///\e
1.194 + typedef typename Graph::Node Node;
1.195 + ///\e
1.196 + typedef typename Graph::NodeIt NodeIt;
1.197 + ///\e
1.198 + typedef typename Graph::Edge Edge;
1.199 + ///\e
1.200 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.201 +
1.202 + ///The type of the length of the edges.
1.203 + typedef typename TR::LengthMap::Value Value;
1.204 + ///The type of the map that stores the edge lengths.
1.205 + typedef typename TR::LengthMap LengthMap;
1.206 + ///\brief The type of the map that stores the last
1.207 + ///edges of the shortest paths.
1.208 + typedef typename TR::PredMap PredMap;
1.209 + ///\brief The type of the map that stores the last but one
1.210 + ///nodes of the shortest paths.
1.211 + typedef typename TR::PredNodeMap PredNodeMap;
1.212 + ///The type of the map indicating if a node is reached.
1.213 + typedef typename TR::ReachedMap ReachedMap;
1.214 + ///The type of the map that stores the dists of the nodes.
1.215 + typedef typename TR::DistMap DistMap;
1.216 + ///The heap type used by the dijkstra algorithm.
1.217 + typedef typename TR::Heap Heap;
1.218 + private:
1.219 + /// Pointer to the underlying graph.
1.220 + const Graph *G;
1.221 + /// Pointer to the length map
1.222 + const LengthMap *length;
1.223 + ///Pointer to the map of predecessors edges.
1.224 + PredMap *_pred;
1.225 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.226 + bool local_pred;
1.227 + ///Pointer to the map of predecessors nodes.
1.228 + PredNodeMap *_predNode;
1.229 + ///Indicates if \ref _predNode is locally allocated (\c true) or not.
1.230 + bool local_predNode;
1.231 + ///Pointer to the map of distances.
1.232 + DistMap *_dist;
1.233 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.234 + bool local_dist;
1.235 + ///Pointer to the map of reached status of the nodes.
1.236 + ReachedMap *_reached;
1.237 + ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.238 + bool local_reached;
1.239 +
1.240 + ///The source node of the last execution.
1.241 + Node source;
1.242 +
1.243 + ///Creates the maps if necessary.
1.244 +
1.245 + ///\todo Error if \c G or are \c NULL. What about \c length?
1.246 + ///\todo Better memory allocation (instead of new).
1.247 + void create_maps()
1.248 + {
1.249 + if(!_pred) {
1.250 + local_pred = true;
1.251 + _pred = Traits::createPredMap(*G);
1.252 + }
1.253 + if(!_predNode) {
1.254 + local_predNode = true;
1.255 + _predNode = Traits::createPredNodeMap(*G);
1.256 + }
1.257 + if(!_dist) {
1.258 + local_dist = true;
1.259 + _dist = Traits::createDistMap(*G);
1.260 + }
1.261 + if(!_reached) {
1.262 + local_reached = true;
1.263 + _reached = Traits::createReachedMap(*G);
1.264 + }
1.265 + }
1.266 +
1.267 + public :
1.268 +
1.269 + ///\name Named template parameters
1.270 +
1.271 + ///@{
1.272 +
1.273 + template <class T>
1.274 + struct DefPredMapTraits : public Traits {
1.275 + typedef T PredMap;
1.276 + static PredMap *createPredMap(const Graph &G)
1.277 + {
1.278 + throw UninitializedParameter();
1.279 + }
1.280 + };
1.281 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.282 +
1.283 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.284 + ///
1.285 + template <class T>
1.286 + class DefPredMap : public Dijkstra< Graph,
1.287 + LengthMap,
1.288 + DefPredMapTraits<T> > { };
1.289 +
1.290 + template <class T>
1.291 + struct DefPredNodeMapTraits : public Traits {
1.292 + typedef T PredNodeMap;
1.293 + static PredNodeMap *createPredNodeMap(const Graph &G)
1.294 + {
1.295 + throw UninitializedParameter();
1.296 + }
1.297 + };
1.298 + ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.299 +
1.300 + ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.301 + ///
1.302 + template <class T>
1.303 + class DefPredNodeMap : public Dijkstra< Graph,
1.304 + LengthMap,
1.305 + DefPredNodeMapTraits<T> > { };
1.306 +
1.307 + template <class T>
1.308 + struct DefDistMapTraits : public Traits {
1.309 + typedef T DistMap;
1.310 + static DistMap *createDistMap(const Graph &G)
1.311 + {
1.312 + throw UninitializedParameter();
1.313 + }
1.314 + };
1.315 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.316 +
1.317 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.318 + ///
1.319 + template <class T>
1.320 + class DefDistMap : public Dijkstra< Graph,
1.321 + LengthMap,
1.322 + DefDistMapTraits<T> > { };
1.323 +
1.324 + template <class T>
1.325 + struct DefReachedMapTraits : public Traits {
1.326 + typedef T ReachedMap;
1.327 + static ReachedMap *createReachedMap(const Graph &G)
1.328 + {
1.329 + throw UninitializedParameter();
1.330 + }
1.331 + };
1.332 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.333 +
1.334 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.335 + ///
1.336 + template <class T>
1.337 + class DefReachedMap : public Dijkstra< Graph,
1.338 + LengthMap,
1.339 + DefReachedMapTraits<T> > { };
1.340 +
1.341 + struct DefGraphReachedMapTraits : public Traits {
1.342 + typedef typename Graph::NodeMap<bool> ReachedMap;
1.343 + static ReachedMap *createReachedMap(const Graph &G)
1.344 + {
1.345 + return new ReachedMap(G);
1.346 + }
1.347 + };
1.348 + ///\brief \ref named-templ-param "Named parameter"
1.349 + ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
1.350 + ///
1.351 + ///\ref named-templ-param "Named parameter"
1.352 + ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
1.353 + ///If you don't set it explicitely, it will be automatically allocated.
1.354 + template <class T>
1.355 + class DefReachedMapToBeDefaultMap :
1.356 + public Dijkstra< Graph,
1.357 + LengthMap,
1.358 + DefGraphReachedMapTraits> { };
1.359 +
1.360 + ///@}
1.361 +
1.362 +
1.363 + private:
1.364 + typename Graph::template NodeMap<int> _heap_map;
1.365 + Heap _heap;
1.366 + public:
1.367 +
1.368 + ///Constructor.
1.369 +
1.370 + ///\param _G the graph the algorithm will run on.
1.371 + ///\param _length the length map used by the algorithm.
1.372 + Dijkstra(const Graph& _G, const LengthMap& _length) :
1.373 + G(&_G), length(&_length),
1.374 + _pred(NULL), local_pred(false),
1.375 + _predNode(NULL), local_predNode(false),
1.376 + _dist(NULL), local_dist(false),
1.377 + _reached(NULL), local_reached(false),
1.378 + _heap_map(*G,-1),_heap(_heap_map)
1.379 + { }
1.380 +
1.381 + ///Destructor.
1.382 + ~Dijkstra()
1.383 + {
1.384 + if(local_pred) delete _pred;
1.385 + if(local_predNode) delete _predNode;
1.386 + if(local_dist) delete _dist;
1.387 + if(local_reached) delete _reached;
1.388 + }
1.389 +
1.390 + ///Sets the length map.
1.391 +
1.392 + ///Sets the length map.
1.393 + ///\return <tt> (*this) </tt>
1.394 + Dijkstra &lengthMap(const LengthMap &m)
1.395 + {
1.396 + length = &m;
1.397 + return *this;
1.398 + }
1.399 +
1.400 + ///Sets the map storing the predecessor edges.
1.401 +
1.402 + ///Sets the map storing the predecessor edges.
1.403 + ///If you don't use this function before calling \ref run(),
1.404 + ///it will allocate one. The destuctor deallocates this
1.405 + ///automatically allocated map, of course.
1.406 + ///\return <tt> (*this) </tt>
1.407 + Dijkstra &predMap(PredMap &m)
1.408 + {
1.409 + if(local_pred) {
1.410 + delete _pred;
1.411 + local_pred=false;
1.412 + }
1.413 + _pred = &m;
1.414 + return *this;
1.415 + }
1.416 +
1.417 + ///Sets the map storing the predecessor nodes.
1.418 +
1.419 + ///Sets the map storing the predecessor nodes.
1.420 + ///If you don't use this function before calling \ref run(),
1.421 + ///it will allocate one. The destuctor deallocates this
1.422 + ///automatically allocated map, of course.
1.423 + ///\return <tt> (*this) </tt>
1.424 + Dijkstra &predNodeMap(PredNodeMap &m)
1.425 + {
1.426 + if(local_predNode) {
1.427 + delete _predNode;
1.428 + local_predNode=false;
1.429 + }
1.430 + _predNode = &m;
1.431 + return *this;
1.432 + }
1.433 +
1.434 + ///Sets the map storing the distances calculated by the algorithm.
1.435 +
1.436 + ///Sets the map storing the distances calculated by the algorithm.
1.437 + ///If you don't use this function before calling \ref run(),
1.438 + ///it will allocate one. The destuctor deallocates this
1.439 + ///automatically allocated map, of course.
1.440 + ///\return <tt> (*this) </tt>
1.441 + Dijkstra &distMap(DistMap &m)
1.442 + {
1.443 + if(local_dist) {
1.444 + delete _dist;
1.445 + local_dist=false;
1.446 + }
1.447 + _dist = &m;
1.448 + return *this;
1.449 + }
1.450 +
1.451 + private:
1.452 + void finalizeNodeData(Node v,Value dst)
1.453 + {
1.454 + _reached->set(v,true);
1.455 + _dist->set(v, dst);
1.456 + _predNode->set(v,G->source((*_pred)[v]));
1.457 + }
1.458 +
1.459 + public:
1.460 + ///\name Excetution control
1.461 + ///The simplest way to execute the algorithm is to use
1.462 + ///\ref run().
1.463 + ///\n
1.464 + ///It you need more control on the execution,
1.465 + ///first you must call \ref init(), then you can add several source nodes
1.466 + ///with \ref addSource(). Finally \ref start() will perform the actual path
1.467 + ///computation.
1.468 +
1.469 + ///@{
1.470 +
1.471 + ///Initializes the internal data structures.
1.472 +
1.473 + ///Initializes the internal data structures.
1.474 + ///
1.475 + ///\todo _heap_map's type could also be in the traits class.
1.476 + void init()
1.477 + {
1.478 + create_maps();
1.479 +
1.480 + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.481 + _pred->set(u,INVALID);
1.482 + _predNode->set(u,INVALID);
1.483 + ///\todo *_reached is not set to false.
1.484 + _heap_map.set(u,Heap::PRE_HEAP);
1.485 + }
1.486 + }
1.487 +
1.488 + ///Adds a new source node.
1.489 +
1.490 + ///Adds a new source node the the priority heap.
1.491 + ///It checks if the node has already been added to the heap.
1.492 + ///
1.493 + ///The optional second parameter is the initial distance of the node.
1.494 + ///
1.495 + ///\todo Do we really want to check it?
1.496 + void addSource(Node s,Value dst=0)
1.497 + {
1.498 + source = s;
1.499 + if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
1.500 + }
1.501 +
1.502 + void processNode()
1.503 + {
1.504 + Node v=_heap.top();
1.505 + Value oldvalue=_heap[v];
1.506 + _heap.pop();
1.507 + finalizeNodeData(v,oldvalue);
1.508 +
1.509 + for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
1.510 + Node w=G->target(e);
1.511 + switch(_heap.state(w)) {
1.512 + case Heap::PRE_HEAP:
1.513 + _heap.push(w,oldvalue+(*length)[e]);
1.514 + _pred->set(w,e);
1.515 +// _predNode->set(w,v);
1.516 + break;
1.517 + case Heap::IN_HEAP:
1.518 + if ( oldvalue+(*length)[e] < _heap[w] ) {
1.519 + _heap.decrease(w, oldvalue+(*length)[e]);
1.520 + _pred->set(w,e);
1.521 +// _predNode->set(w,v);
1.522 + }
1.523 + break;
1.524 + case Heap::POST_HEAP:
1.525 + break;
1.526 + }
1.527 + }
1.528 + }
1.529 +
1.530 + ///Executes the algorithm.
1.531 +
1.532 + ///Executes the algorithm.
1.533 + ///
1.534 + ///\pre init() must be called and at least one node should be added
1.535 + ///with addSource() before using this function.
1.536 + ///
1.537 + ///This method runs the %Dijkstra algorithm from the root node(s)
1.538 + ///in order to
1.539 + ///compute the
1.540 + ///shortest path to each node. The algorithm computes
1.541 + ///- The shortest path tree.
1.542 + ///- The distance of each node from the root(s).
1.543 + ///
1.544 + void start()
1.545 + {
1.546 + while ( !_heap.empty() ) processNode();
1.547 + }
1.548 +
1.549 + ///Executes the algorithm until \c dest is reached.
1.550 +
1.551 + ///Executes the algorithm until \c dest is reached.
1.552 + ///
1.553 + ///\pre init() must be called and at least one node should be added
1.554 + ///with addSource() before using this function.
1.555 + ///
1.556 + ///This method runs the %Dijkstra algorithm from the root node(s)
1.557 + ///in order to
1.558 + ///compute the
1.559 + ///shortest path to \c dest. The algorithm computes
1.560 + ///- The shortest path to \c dest.
1.561 + ///- The distance of \c dest from the root(s).
1.562 + ///
1.563 + void start(Node dest)
1.564 + {
1.565 + while ( !_heap.empty() && _heap.top()!=dest ) processNode();
1.566 + if ( _heap.top()==dest ) finalizeNodeData(_heap.top());
1.567 + }
1.568 +
1.569 + ///Executes the algorithm until a condition is met.
1.570 +
1.571 + ///Executes the algorithm until a condition is met.
1.572 + ///
1.573 + ///\pre init() must be called and at least one node should be added
1.574 + ///with addSource() before using this function.
1.575 + ///
1.576 + ///\param nm must be a bool (or convertible) node map. The algorithm
1.577 + ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
1.578 + template<class NM>
1.579 + void start(const NM &nm)
1.580 + {
1.581 + while ( !_heap.empty() && !mn[_heap.top()] ) processNode();
1.582 + if ( !_heap.empty() ) finalizeNodeData(_heap.top());
1.583 + }
1.584 +
1.585 + ///Runs %Dijkstra algorithm from node \c s.
1.586 +
1.587 + ///This method runs the %Dijkstra algorithm from a root node \c s
1.588 + ///in order to
1.589 + ///compute the
1.590 + ///shortest path to each node. The algorithm computes
1.591 + ///- The shortest path tree.
1.592 + ///- The distance of each node from the root.
1.593 + ///
1.594 + ///\note d.run(s) is just a shortcut of the following code.
1.595 + ///\code
1.596 + /// d.init();
1.597 + /// d.addSource(s);
1.598 + /// d.start();
1.599 + ///\endcode
1.600 + void run(Node s) {
1.601 + init();
1.602 + addSource(s);
1.603 + start();
1.604 + }
1.605 +
1.606 + ///Finds the shortest path between \c s and \c t.
1.607 +
1.608 + ///Finds the shortest path between \c s and \c t.
1.609 + ///
1.610 + ///\return The length of the shortest s---t path if there exists one,
1.611 + ///0 otherwise.
1.612 + ///\note Apart from the return value, d.run(s) is
1.613 + ///just a shortcut of the following code.
1.614 + ///\code
1.615 + /// d.init();
1.616 + /// d.addSource(s);
1.617 + /// d.start(t);
1.618 + ///\endcode
1.619 + Value run(Node s,Node t) {
1.620 + init();
1.621 + addSource(s);
1.622 + start(t);
1.623 + return (*_pred)[t]==INVALID?0:(*_dist)[t];
1.624 + }
1.625 +
1.626 + ///@}
1.627 +
1.628 + ///\name Query Functions
1.629 + ///The result of the %Dijkstra algorithm can be obtained using these
1.630 + ///functions.\n
1.631 + ///Before the use of these functions,
1.632 + ///either run() or start() must be called.
1.633 +
1.634 + ///@{
1.635 +
1.636 + ///The distance of a node from the root.
1.637 +
1.638 + ///Returns the distance of a node from the root.
1.639 + ///\pre \ref run() must be called before using this function.
1.640 + ///\warning If node \c v in unreachable from the root the return value
1.641 + ///of this funcion is undefined.
1.642 + Value dist(Node v) const { return (*_dist)[v]; }
1.643 +
1.644 + ///Returns the 'previous edge' of the shortest path tree.
1.645 +
1.646 + ///For a node \c v it returns the 'previous edge' of the shortest path tree,
1.647 + ///i.e. it returns the last edge of a shortest path from the root to \c
1.648 + ///v. It is \ref INVALID
1.649 + ///if \c v is unreachable from the root or if \c v=s. The
1.650 + ///shortest path tree used here is equal to the shortest path tree used in
1.651 + ///\ref predNode(Node v). \pre \ref run() must be called before using
1.652 + ///this function.
1.653 + ///\todo predEdge could be a better name.
1.654 + Edge pred(Node v) const { return (*_pred)[v]; }
1.655 +
1.656 + ///Returns the 'previous node' of the shortest path tree.
1.657 +
1.658 + ///For a node \c v it returns the 'previous node' of the shortest path tree,
1.659 + ///i.e. it returns the last but one node from a shortest path from the
1.660 + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
1.661 + ///\c v=s. The shortest path tree used here is equal to the shortest path
1.662 + ///tree used in \ref pred(Node v). \pre \ref run() must be called before
1.663 + ///using this function.
1.664 + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.665 + G->source((*_pred)[v]); }
1.666 +
1.667 + ///Returns a reference to the NodeMap of distances.
1.668 +
1.669 + ///Returns a reference to the NodeMap of distances. \pre \ref run() must
1.670 + ///be called before using this function.
1.671 + const DistMap &distMap() const { return *_dist;}
1.672 +
1.673 + ///Returns a reference to the shortest path tree map.
1.674 +
1.675 + ///Returns a reference to the NodeMap of the edges of the
1.676 + ///shortest path tree.
1.677 + ///\pre \ref run() must be called before using this function.
1.678 + const PredMap &predMap() const { return *_pred;}
1.679 +
1.680 + ///Returns a reference to the map of nodes of shortest paths.
1.681 +
1.682 + ///Returns a reference to the NodeMap of the last but one nodes of the
1.683 + ///shortest path tree.
1.684 + ///\pre \ref run() must be called before using this function.
1.685 + const PredNodeMap &predNodeMap() const { return *_predNode;}
1.686 +
1.687 + ///Checks if a node is reachable from the root.
1.688 +
1.689 + ///Returns \c true if \c v is reachable from the root.
1.690 + ///\warning If the algorithm is started from multiple nodes,
1.691 + ///this function may give false result for the source nodes.
1.692 + ///\pre \ref run() must be called before using this function.
1.693 + ///
1.694 + bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
1.695 +
1.696 + ///@}
1.697 + };
1.698 +
1.699 + /// Default traits used by \ref DijkstraWizard
1.700 +
1.701 + /// To make it easier to use Dijkstra algorithm we have created a wizard class.
1.702 + /// This \ref DijkstraWizard class needs default traits, as well as the \ref Dijkstra class.
1.703 + /// The \ref DijkstraWizardBase is a class to be the default traits of the
1.704 + /// \ref DijkstraWizard class.
1.705 + template<class GR,class LM>
1.706 + class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
1.707 + {
1.708 +
1.709 + typedef DijkstraDefaultTraits<GR,LM> Base;
1.710 + protected:
1.711 + /// Pointer to the underlying graph.
1.712 + void *_g;
1.713 + /// Pointer to the length map
1.714 + void *_length;
1.715 + ///Pointer to the map of predecessors edges.
1.716 + void *_pred;
1.717 + ///Pointer to the map of predecessors nodes.
1.718 + void *_predNode;
1.719 + ///Pointer to the map of distances.
1.720 + void *_dist;
1.721 + ///Pointer to the source node.
1.722 + void *_source;
1.723 +
1.724 + /// Type of the nodes in the graph.
1.725 + typedef typename Base::Graph::Node Node;
1.726 +
1.727 + public:
1.728 + /// Constructor.
1.729 +
1.730 + /// This constructor does not require parameters, therefore it initiates
1.731 + /// all of the attributes to default values (0, INVALID).
1.732 + DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
1.733 + _dist(0), _source(INVALID) {}
1.734 +
1.735 + /// Constructor.
1.736 +
1.737 + /// This constructor requires some parameters, listed in the parameters list.
1.738 + /// Others are initiated to 0.
1.739 + /// \param g is the initial value of \ref _g
1.740 + /// \param l is the initial value of \ref _length
1.741 + /// \param s is the initial value of \ref _source
1.742 + DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
1.743 + _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
1.744 + _dist(0), _source((void *)&s) {}
1.745 +
1.746 + };
1.747 +
1.748 + /// A class to make easier the usage of Dijkstra algorithm
1.749 +
1.750 + /// This class is created to make it easier to use Dijkstra algorithm.
1.751 + /// It uses the functions and features of the plain \ref Dijkstra,
1.752 + /// but it is much more simple to use it.
1.753 + ///
1.754 + /// Simplicity means that the way to change the types defined
1.755 + /// in the traits class is based on functions that returns the new class
1.756 + /// and not on templatable built-in classes. When using the plain \ref Dijkstra
1.757 + /// the new class with the modified type comes from the original class by using the ::
1.758 + /// operator. In the case of \ref DijkstraWizard only a function have to be called and it will
1.759 + /// return the needed class.
1.760 + ///
1.761 + /// It does not have own \ref run method. When its \ref run method is called
1.762 + /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
1.763 + /// method of it.
1.764 + template<class TR>
1.765 + class DijkstraWizard : public TR
1.766 + {
1.767 + typedef TR Base;
1.768 +
1.769 + ///The type of the underlying graph.
1.770 + typedef typename TR::Graph Graph;
1.771 + //\e
1.772 + typedef typename Graph::Node Node;
1.773 + //\e
1.774 + typedef typename Graph::NodeIt NodeIt;
1.775 + //\e
1.776 + typedef typename Graph::Edge Edge;
1.777 + //\e
1.778 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.779 +
1.780 + ///The type of the map that stores the edge lengths.
1.781 + typedef typename TR::LengthMap LengthMap;
1.782 + ///The type of the length of the edges.
1.783 + typedef typename LengthMap::Value Value;
1.784 + ///\brief The type of the map that stores the last
1.785 + ///edges of the shortest paths.
1.786 + typedef typename TR::PredMap PredMap;
1.787 + ///\brief The type of the map that stores the last but one
1.788 + ///nodes of the shortest paths.
1.789 + typedef typename TR::PredNodeMap PredNodeMap;
1.790 + ///The type of the map that stores the dists of the nodes.
1.791 + typedef typename TR::DistMap DistMap;
1.792 +
1.793 + ///The heap type used by the dijkstra algorithm.
1.794 + typedef typename TR::Heap Heap;
1.795 +public:
1.796 + /// Constructor.
1.797 + DijkstraWizard() : TR() {}
1.798 +
1.799 + /// Constructor that requires parameters.
1.800 +
1.801 + /// Constructor that requires parameters.
1.802 + /// These parameters will be the default values for the traits class.
1.803 + DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
1.804 + TR(g,l,s) {}
1.805 +
1.806 + ///Copy constructor
1.807 + DijkstraWizard(const TR &b) : TR(b) {}
1.808 +
1.809 + ~DijkstraWizard() {}
1.810 +
1.811 + ///Runs Dijkstra algorithm from a given node.
1.812 +
1.813 + ///Runs Dijkstra algorithm from a given node.
1.814 + ///The node can be given by the \ref source function.
1.815 + void run()
1.816 + {
1.817 + if(_source==0) throw UninitializedParameter();
1.818 + Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
1.819 + if(_pred) Dij.predMap(*(PredMap*)_pred);
1.820 + if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
1.821 + if(_dist) Dij.distMap(*(DistMap*)_dist);
1.822 + Dij.run(*(Node*)_source);
1.823 + }
1.824 +
1.825 + ///Runs Dijkstra algorithm from the given node.
1.826 +
1.827 + ///Runs Dijkstra algorithm from the given node.
1.828 + ///\param s is the given source.
1.829 + void run(Node s)
1.830 + {
1.831 + _source=(void *)&s;
1.832 + run();
1.833 + }
1.834 +
1.835 + template<class T>
1.836 + struct DefPredMapBase : public Base {
1.837 + typedef T PredMap;
1.838 + static PredMap *createPredMap(const Graph &G) { return 0; };
1.839 + DefPredMapBase(const Base &b) : Base(b) {}
1.840 + };
1.841 +
1.842 + /// \ref named-templ-param "Named parameter" function for setting PredMap type
1.843 +
1.844 + /// \ref named-templ-param "Named parameter" function for setting PredMap type
1.845 + ///
1.846 + template<class T>
1.847 + DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
1.848 + {
1.849 + _pred=(void *)&t;
1.850 + return DijkstraWizard<DefPredMapBase<T> >(*this);
1.851 + }
1.852 +
1.853 +
1.854 + template<class T>
1.855 + struct DefPredNodeMapBase : public Base {
1.856 + typedef T PredNodeMap;
1.857 + static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1.858 + DefPredNodeMapBase(const Base &b) : Base(b) {}
1.859 + };
1.860 +
1.861 + /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
1.862 +
1.863 + /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
1.864 + ///
1.865 + template<class T>
1.866 + DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.867 + {
1.868 + _predNode=(void *)&t;
1.869 + return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
1.870 + }
1.871 +
1.872 + template<class T>
1.873 + struct DefDistMapBase : public Base {
1.874 + typedef T DistMap;
1.875 + static DistMap *createDistMap(const Graph &G) { return 0; };
1.876 + DefDistMapBase(const Base &b) : Base(b) {}
1.877 + };
1.878 +
1.879 + /// \ref named-templ-param "Named parameter" function for setting DistMap type
1.880 +
1.881 + /// \ref named-templ-param "Named parameter" function for setting DistMap type
1.882 + ///
1.883 + template<class T>
1.884 + DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1.885 + {
1.886 + _dist=(void *)&t;
1.887 + return DijkstraWizard<DefDistMapBase<T> >(*this);
1.888 + }
1.889 +
1.890 + /// Sets the source node, from which the Dijkstra algorithm runs.
1.891 +
1.892 + /// Sets the source node, from which the Dijkstra algorithm runs.
1.893 + /// \param s is the source node.
1.894 + DijkstraWizard<TR> &source(Node s)
1.895 + {
1.896 + source=(void *)&s;
1.897 + return *this;
1.898 + }
1.899 +
1.900 + };
1.901 +
1.902 + ///\e
1.903 +
1.904 + ///\todo Please document...
1.905 + ///
1.906 + template<class GR, class LM>
1.907 + DijkstraWizard<DijkstraWizardBase<GR,LM> >
1.908 + dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1.909 + {
1.910 + return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1.911 + }
1.912 +
1.913 +/// @}
1.914 +
1.915 +} //END OF NAMESPACE LEMON
1.916 +
1.917 +#endif
1.918 +
2.1 --- a/src/work/alpar/dijkstra.h Sun Feb 06 20:08:25 2005 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,915 +0,0 @@
2.4 -/* -*- C++ -*-
2.5 - * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
2.6 - *
2.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
2.9 - *
2.10 - * Permission to use, modify and distribute this software is granted
2.11 - * provided that this copyright notice appears in all copies. For
2.12 - * precise terms see the accompanying LICENSE file.
2.13 - *
2.14 - * This software is provided "AS IS" with no warranty of any kind,
2.15 - * express or implied, and with no claim as to its suitability for any
2.16 - * purpose.
2.17 - *
2.18 - */
2.19 -
2.20 -#ifndef LEMON_DIJKSTRA_H
2.21 -#define LEMON_DIJKSTRA_H
2.22 -
2.23 -///\ingroup flowalgs
2.24 -///\file
2.25 -///\brief Dijkstra algorithm.
2.26 -
2.27 -#include <lemon/list_graph.h>
2.28 -#include <lemon/bin_heap.h>
2.29 -#include <lemon/invalid.h>
2.30 -#include <lemon/error.h>
2.31 -#include <lemon/maps.h>
2.32 -
2.33 -namespace lemon {
2.34 -
2.35 -
2.36 -/// \addtogroup flowalgs
2.37 -/// @{
2.38 -
2.39 - ///Default traits class of Dijkstra class.
2.40 -
2.41 - ///Default traits class of Dijkstra class.
2.42 - ///\param GR Graph type.
2.43 - ///\param LM Type of length map.
2.44 - template<class GR, class LM>
2.45 - struct DijkstraDefaultTraits
2.46 - {
2.47 - ///The graph type the algorithm runs on.
2.48 - typedef GR Graph;
2.49 - ///The type of the map that stores the edge lengths.
2.50 -
2.51 - ///The type of the map that stores the edge lengths.
2.52 - ///It must meet the \ref concept::ReadMap "ReadMap" concept.
2.53 - typedef LM LengthMap;
2.54 - //The type of the length of the edges.
2.55 - typedef typename LM::Value Value;
2.56 - ///The heap type used by Dijkstra algorithm.
2.57 -
2.58 - ///The heap type used by Dijkstra algorithm.
2.59 - ///
2.60 - ///\sa BinHeap
2.61 - ///\sa Dijkstra
2.62 - typedef BinHeap<typename Graph::Node,
2.63 - typename LM::Value,
2.64 - typename GR::template NodeMap<int>,
2.65 - std::less<Value> > Heap;
2.66 -
2.67 - ///\brief The type of the map that stores the last
2.68 - ///edges of the shortest paths.
2.69 - ///
2.70 - ///The type of the map that stores the last
2.71 - ///edges of the shortest paths.
2.72 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.73 - ///
2.74 - typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
2.75 - ///Instantiates a PredMap.
2.76 -
2.77 - ///This function instantiates a \ref PredMap.
2.78 - ///\param G is the graph, to which we would like to define the PredMap.
2.79 - ///\todo The graph alone may be insufficient for the initialization
2.80 - static PredMap *createPredMap(const GR &G)
2.81 - {
2.82 - return new PredMap(G);
2.83 - }
2.84 - ///\brief The type of the map that stores the last but one
2.85 - ///nodes of the shortest paths.
2.86 - ///
2.87 - ///The type of the map that stores the last but one
2.88 - ///nodes of the shortest paths.
2.89 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.90 - ///
2.91 - typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
2.92 - ///Instantiates a PredNodeMap.
2.93 -
2.94 - ///This function instantiates a \ref PredNodeMap.
2.95 - ///\param G is the graph, to which we would like to define the \ref PredNodeMap
2.96 - static PredNodeMap *createPredNodeMap(const GR &G)
2.97 - {
2.98 - return new PredNodeMap();
2.99 - }
2.100 -
2.101 - ///The type of the map that stores whether a nodes is reached.
2.102 -
2.103 - ///The type of the map that stores whether a nodes is reached.
2.104 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.105 - ///By default it is a NullMap.
2.106 - ///\todo If it is set to a real map, Dijkstra::reached() should read this.
2.107 - ///\todo named parameter to set this type, function to read and write.
2.108 - typedef NullMap<typename Graph::Node,bool> ReachedMap;
2.109 - ///Instantiates a ReachedMap.
2.110 -
2.111 - ///This function instantiates a \ref ReachedMap.
2.112 - ///\param G is the graph, to which we would like to define the \ref ReachedMap
2.113 - static ReachedMap *createReachedMap(const GR &G)
2.114 - {
2.115 - return new ReachedMap();
2.116 - }
2.117 - ///The type of the map that stores the dists of the nodes.
2.118 -
2.119 - ///The type of the map that stores the dists of the nodes.
2.120 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.121 - ///
2.122 - typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
2.123 - ///Instantiates a DistMap.
2.124 -
2.125 - ///This function instantiates a \ref DistMap.
2.126 - ///\param G is the graph, to which we would like to define the \ref DistMap
2.127 - static DistMap *createDistMap(const GR &G)
2.128 - {
2.129 - return new DistMap(G);
2.130 - }
2.131 - };
2.132 -
2.133 - ///%Dijkstra algorithm class.
2.134 -
2.135 - ///This class provides an efficient implementation of %Dijkstra algorithm.
2.136 - ///The edge lengths are passed to the algorithm using a
2.137 - ///\ref concept::ReadMap "ReadMap",
2.138 - ///so it is easy to change it to any kind of length.
2.139 - ///
2.140 - ///The type of the length is determined by the
2.141 - ///\ref concept::ReadMap::Value "Value" of the length map.
2.142 - ///
2.143 - ///It is also possible to change the underlying priority heap.
2.144 - ///
2.145 - ///\param GR The graph type the algorithm runs on. The default value is
2.146 - ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
2.147 - ///is only passed to \ref DijkstraDefaultTraits.
2.148 - ///\param LM This read-only
2.149 - ///EdgeMap
2.150 - ///determines the
2.151 - ///lengths of the edges. It is read once for each edge, so the map
2.152 - ///may involve in relatively time consuming process to compute the edge
2.153 - ///length if it is necessary. The default map type is
2.154 - ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
2.155 - ///The value of LM is not used directly by Dijkstra, it
2.156 - ///is only passed to \ref DijkstraDefaultTraits.
2.157 - ///\param TR Traits class to set various data types used by the algorithm.
2.158 - ///The default traits class is
2.159 - ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
2.160 - ///See \ref DijkstraDefaultTraits for the documentation of
2.161 - ///a Dijkstra traits class.
2.162 - ///
2.163 - ///\author Jacint Szabo and Alpar Juttner
2.164 - ///\todo A compare object would be nice.
2.165 -
2.166 -#ifdef DOXYGEN
2.167 - template <typename GR,
2.168 - typename LM,
2.169 - typename TR>
2.170 -#else
2.171 - template <typename GR=ListGraph,
2.172 - typename LM=typename GR::template EdgeMap<int>,
2.173 - typename TR=DijkstraDefaultTraits<GR,LM> >
2.174 -#endif
2.175 - class Dijkstra {
2.176 - public:
2.177 - /**
2.178 - * \brief \ref Exception for uninitialized parameters.
2.179 - *
2.180 - * This error represents problems in the initialization
2.181 - * of the parameters of the algorithms.
2.182 - */
2.183 - class UninitializedParameter : public lemon::UninitializedParameter {
2.184 - public:
2.185 - virtual const char* exceptionName() const {
2.186 - return "lemon::Dijsktra::UninitializedParameter";
2.187 - }
2.188 - };
2.189 -
2.190 - typedef TR Traits;
2.191 - ///The type of the underlying graph.
2.192 - typedef typename TR::Graph Graph;
2.193 - ///\e
2.194 - typedef typename Graph::Node Node;
2.195 - ///\e
2.196 - typedef typename Graph::NodeIt NodeIt;
2.197 - ///\e
2.198 - typedef typename Graph::Edge Edge;
2.199 - ///\e
2.200 - typedef typename Graph::OutEdgeIt OutEdgeIt;
2.201 -
2.202 - ///The type of the length of the edges.
2.203 - typedef typename TR::LengthMap::Value Value;
2.204 - ///The type of the map that stores the edge lengths.
2.205 - typedef typename TR::LengthMap LengthMap;
2.206 - ///\brief The type of the map that stores the last
2.207 - ///edges of the shortest paths.
2.208 - typedef typename TR::PredMap PredMap;
2.209 - ///\brief The type of the map that stores the last but one
2.210 - ///nodes of the shortest paths.
2.211 - typedef typename TR::PredNodeMap PredNodeMap;
2.212 - ///The type of the map indicating if a node is reached.
2.213 - typedef typename TR::ReachedMap ReachedMap;
2.214 - ///The type of the map that stores the dists of the nodes.
2.215 - typedef typename TR::DistMap DistMap;
2.216 - ///The heap type used by the dijkstra algorithm.
2.217 - typedef typename TR::Heap Heap;
2.218 - private:
2.219 - /// Pointer to the underlying graph.
2.220 - const Graph *G;
2.221 - /// Pointer to the length map
2.222 - const LengthMap *length;
2.223 - ///Pointer to the map of predecessors edges.
2.224 - PredMap *_pred;
2.225 - ///Indicates if \ref _pred is locally allocated (\c true) or not.
2.226 - bool local_pred;
2.227 - ///Pointer to the map of predecessors nodes.
2.228 - PredNodeMap *_predNode;
2.229 - ///Indicates if \ref _predNode is locally allocated (\c true) or not.
2.230 - bool local_predNode;
2.231 - ///Pointer to the map of distances.
2.232 - DistMap *_dist;
2.233 - ///Indicates if \ref _dist is locally allocated (\c true) or not.
2.234 - bool local_dist;
2.235 - ///Pointer to the map of reached status of the nodes.
2.236 - ReachedMap *_reached;
2.237 - ///Indicates if \ref _reached is locally allocated (\c true) or not.
2.238 - bool local_reached;
2.239 -
2.240 - ///The source node of the last execution.
2.241 - Node source;
2.242 -
2.243 - ///Creates the maps if necessary.
2.244 -
2.245 - ///\todo Error if \c G or are \c NULL. What about \c length?
2.246 - ///\todo Better memory allocation (instead of new).
2.247 - void create_maps()
2.248 - {
2.249 - if(!_pred) {
2.250 - local_pred = true;
2.251 - _pred = Traits::createPredMap(*G);
2.252 - }
2.253 - if(!_predNode) {
2.254 - local_predNode = true;
2.255 - _predNode = Traits::createPredNodeMap(*G);
2.256 - }
2.257 - if(!_dist) {
2.258 - local_dist = true;
2.259 - _dist = Traits::createDistMap(*G);
2.260 - }
2.261 - if(!_reached) {
2.262 - local_reached = true;
2.263 - _reached = Traits::createReachedMap(*G);
2.264 - }
2.265 - }
2.266 -
2.267 - public :
2.268 -
2.269 - ///\name Named template parameters
2.270 -
2.271 - ///@{
2.272 -
2.273 - template <class T>
2.274 - struct DefPredMapTraits : public Traits {
2.275 - typedef T PredMap;
2.276 - static PredMap *createPredMap(const Graph &G)
2.277 - {
2.278 - throw UninitializedParameter();
2.279 - }
2.280 - };
2.281 - ///\ref named-templ-param "Named parameter" for setting PredMap type
2.282 -
2.283 - ///\ref named-templ-param "Named parameter" for setting PredMap type
2.284 - ///
2.285 - template <class T>
2.286 - class DefPredMap : public Dijkstra< Graph,
2.287 - LengthMap,
2.288 - DefPredMapTraits<T> > { };
2.289 -
2.290 - template <class T>
2.291 - struct DefPredNodeMapTraits : public Traits {
2.292 - typedef T PredNodeMap;
2.293 - static PredNodeMap *createPredNodeMap(const Graph &G)
2.294 - {
2.295 - throw UninitializedParameter();
2.296 - }
2.297 - };
2.298 - ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
2.299 -
2.300 - ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
2.301 - ///
2.302 - template <class T>
2.303 - class DefPredNodeMap : public Dijkstra< Graph,
2.304 - LengthMap,
2.305 - DefPredNodeMapTraits<T> > { };
2.306 -
2.307 - template <class T>
2.308 - struct DefDistMapTraits : public Traits {
2.309 - typedef T DistMap;
2.310 - static DistMap *createDistMap(const Graph &G)
2.311 - {
2.312 - throw UninitializedParameter();
2.313 - }
2.314 - };
2.315 - ///\ref named-templ-param "Named parameter" for setting DistMap type
2.316 -
2.317 - ///\ref named-templ-param "Named parameter" for setting DistMap type
2.318 - ///
2.319 - template <class T>
2.320 - class DefDistMap : public Dijkstra< Graph,
2.321 - LengthMap,
2.322 - DefDistMapTraits<T> > { };
2.323 -
2.324 - template <class T>
2.325 - struct DefReachedMapTraits : public Traits {
2.326 - typedef T ReachedMap;
2.327 - static ReachedMap *createReachedMap(const Graph &G)
2.328 - {
2.329 - throw UninitializedParameter();
2.330 - }
2.331 - };
2.332 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
2.333 -
2.334 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
2.335 - ///
2.336 - template <class T>
2.337 - class DefReachedMap : public Dijkstra< Graph,
2.338 - LengthMap,
2.339 - DefReachedMapTraits<T> > { };
2.340 -
2.341 - struct DefGraphReachedMapTraits : public Traits {
2.342 - typedef typename Graph::NodeMap<bool> ReachedMap;
2.343 - static ReachedMap *createReachedMap(const Graph &G)
2.344 - {
2.345 - return new ReachedMap(G);
2.346 - }
2.347 - };
2.348 - ///\brief \ref named-templ-param "Named parameter"
2.349 - ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
2.350 - ///
2.351 - ///\ref named-templ-param "Named parameter"
2.352 - ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
2.353 - ///If you don't set it explicitely, it will be automatically allocated.
2.354 - template <class T>
2.355 - class DefReachedMapToBeDefaultMap :
2.356 - public Dijkstra< Graph,
2.357 - LengthMap,
2.358 - DefGraphReachedMapTraits> { };
2.359 -
2.360 - ///@}
2.361 -
2.362 -
2.363 - private:
2.364 - typename Graph::template NodeMap<int> _heap_map;
2.365 - Heap _heap;
2.366 - public:
2.367 -
2.368 - ///Constructor.
2.369 -
2.370 - ///\param _G the graph the algorithm will run on.
2.371 - ///\param _length the length map used by the algorithm.
2.372 - Dijkstra(const Graph& _G, const LengthMap& _length) :
2.373 - G(&_G), length(&_length),
2.374 - _pred(NULL), local_pred(false),
2.375 - _predNode(NULL), local_predNode(false),
2.376 - _dist(NULL), local_dist(false),
2.377 - _reached(NULL), local_reached(false),
2.378 - _heap_map(*G,-1),_heap(_heap_map)
2.379 - { }
2.380 -
2.381 - ///Destructor.
2.382 - ~Dijkstra()
2.383 - {
2.384 - if(local_pred) delete _pred;
2.385 - if(local_predNode) delete _predNode;
2.386 - if(local_dist) delete _dist;
2.387 - if(local_reached) delete _reached;
2.388 - }
2.389 -
2.390 - ///Sets the length map.
2.391 -
2.392 - ///Sets the length map.
2.393 - ///\return <tt> (*this) </tt>
2.394 - Dijkstra &lengthMap(const LengthMap &m)
2.395 - {
2.396 - length = &m;
2.397 - return *this;
2.398 - }
2.399 -
2.400 - ///Sets the map storing the predecessor edges.
2.401 -
2.402 - ///Sets the map storing the predecessor edges.
2.403 - ///If you don't use this function before calling \ref run(),
2.404 - ///it will allocate one. The destuctor deallocates this
2.405 - ///automatically allocated map, of course.
2.406 - ///\return <tt> (*this) </tt>
2.407 - Dijkstra &predMap(PredMap &m)
2.408 - {
2.409 - if(local_pred) {
2.410 - delete _pred;
2.411 - local_pred=false;
2.412 - }
2.413 - _pred = &m;
2.414 - return *this;
2.415 - }
2.416 -
2.417 - ///Sets the map storing the predecessor nodes.
2.418 -
2.419 - ///Sets the map storing the predecessor nodes.
2.420 - ///If you don't use this function before calling \ref run(),
2.421 - ///it will allocate one. The destuctor deallocates this
2.422 - ///automatically allocated map, of course.
2.423 - ///\return <tt> (*this) </tt>
2.424 - Dijkstra &predNodeMap(PredNodeMap &m)
2.425 - {
2.426 - if(local_predNode) {
2.427 - delete _predNode;
2.428 - local_predNode=false;
2.429 - }
2.430 - _predNode = &m;
2.431 - return *this;
2.432 - }
2.433 -
2.434 - ///Sets the map storing the distances calculated by the algorithm.
2.435 -
2.436 - ///Sets the map storing the distances calculated by the algorithm.
2.437 - ///If you don't use this function before calling \ref run(),
2.438 - ///it will allocate one. The destuctor deallocates this
2.439 - ///automatically allocated map, of course.
2.440 - ///\return <tt> (*this) </tt>
2.441 - Dijkstra &distMap(DistMap &m)
2.442 - {
2.443 - if(local_dist) {
2.444 - delete _dist;
2.445 - local_dist=false;
2.446 - }
2.447 - _dist = &m;
2.448 - return *this;
2.449 - }
2.450 -
2.451 - private:
2.452 - void finalizeNodeData(Node v,Value dst)
2.453 - {
2.454 - _reached->set(v,true);
2.455 - _dist->set(v, dst);
2.456 - _predNode->set(v,G->source((*_pred)[v]));
2.457 - }
2.458 -
2.459 - public:
2.460 - ///\name Excetution control
2.461 - ///The simplest way to execute the algorithm is to use
2.462 - ///\ref run().
2.463 - ///\n
2.464 - ///It you need more control on the execution,
2.465 - ///first you must call \ref init(), then you can add several source nodes
2.466 - ///with \ref addSource(). Finally \ref start() will perform the actual path
2.467 - ///computation.
2.468 -
2.469 - ///@{
2.470 -
2.471 - ///Initializes the internal data structures.
2.472 -
2.473 - ///Initializes the internal data structures.
2.474 - ///
2.475 - ///\todo _heap_map's type could also be in the traits class.
2.476 - void init()
2.477 - {
2.478 - create_maps();
2.479 -
2.480 - for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
2.481 - _pred->set(u,INVALID);
2.482 - _predNode->set(u,INVALID);
2.483 - ///\todo *_reached is not set to false.
2.484 - _heap_map.set(u,Heap::PRE_HEAP);
2.485 - }
2.486 - }
2.487 -
2.488 - ///Adds a new source node.
2.489 -
2.490 - ///Adds a new source node the the priority heap.
2.491 - ///It checks if the node has already been added to the heap.
2.492 - ///
2.493 - ///The optional second parameter is the initial distance of the node.
2.494 - ///
2.495 - ///\todo Do we really want to check it?
2.496 - void addSource(Node s,Value dst=0)
2.497 - {
2.498 - source = s;
2.499 - if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
2.500 - }
2.501 -
2.502 - void processNode()
2.503 - {
2.504 - Node v=_heap.top();
2.505 - Value oldvalue=_heap[v];
2.506 - _heap.pop();
2.507 - finalizeNodeData(v,oldvalue);
2.508 -
2.509 - for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
2.510 - Node w=G->target(e);
2.511 - switch(_heap.state(w)) {
2.512 - case Heap::PRE_HEAP:
2.513 - _heap.push(w,oldvalue+(*length)[e]);
2.514 - _pred->set(w,e);
2.515 -// _predNode->set(w,v);
2.516 - break;
2.517 - case Heap::IN_HEAP:
2.518 - if ( oldvalue+(*length)[e] < _heap[w] ) {
2.519 - _heap.decrease(w, oldvalue+(*length)[e]);
2.520 - _pred->set(w,e);
2.521 -// _predNode->set(w,v);
2.522 - }
2.523 - break;
2.524 - case Heap::POST_HEAP:
2.525 - break;
2.526 - }
2.527 - }
2.528 - }
2.529 -
2.530 - ///Executes the algorithm.
2.531 -
2.532 - ///Executes the algorithm.
2.533 - ///
2.534 - ///\pre init() must be called and at least one node should be added
2.535 - ///with addSource() before using this function.
2.536 - ///
2.537 - ///This method runs the %Dijkstra algorithm from the root node(s)
2.538 - ///in order to
2.539 - ///compute the
2.540 - ///shortest path to each node. The algorithm computes
2.541 - ///- The shortest path tree.
2.542 - ///- The distance of each node from the root(s).
2.543 - ///
2.544 - void start()
2.545 - {
2.546 - while ( !_heap.empty() ) processNode();
2.547 - }
2.548 -
2.549 - ///Executes the algorithm until \c dest is reached.
2.550 -
2.551 - ///Executes the algorithm until \c dest is reached.
2.552 - ///
2.553 - ///\pre init() must be called and at least one node should be added
2.554 - ///with addSource() before using this function.
2.555 - ///
2.556 - ///This method runs the %Dijkstra algorithm from the root node(s)
2.557 - ///in order to
2.558 - ///compute the
2.559 - ///shortest path to \c dest. The algorithm computes
2.560 - ///- The shortest path to \c dest.
2.561 - ///- The distance of \c dest from the root(s).
2.562 - ///
2.563 - void start(Node dest)
2.564 - {
2.565 - while ( !_heap.empty() && _heap.top()!=dest ) processNode();
2.566 - if ( _heap.top()==dest ) finalizeNodeData(_heap.top());
2.567 - }
2.568 -
2.569 - ///Executes the algorithm until a condition is met.
2.570 -
2.571 - ///Executes the algorithm until a condition is met.
2.572 - ///
2.573 - ///\pre init() must be called and at least one node should be added
2.574 - ///with addSource() before using this function.
2.575 - ///
2.576 - ///\param nm must be a bool (or convertible) node map. The algorithm
2.577 - ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
2.578 - template<class NM>
2.579 - void start(const NM &nm)
2.580 - {
2.581 - while ( !_heap.empty() && !mn[_heap.top()] ) processNode();
2.582 - if ( !_heap.empty() ) finalizeNodeData(_heap.top());
2.583 - }
2.584 -
2.585 - ///Runs %Dijkstra algorithm from node \c s.
2.586 -
2.587 - ///This method runs the %Dijkstra algorithm from a root node \c s
2.588 - ///in order to
2.589 - ///compute the
2.590 - ///shortest path to each node. The algorithm computes
2.591 - ///- The shortest path tree.
2.592 - ///- The distance of each node from the root.
2.593 - ///
2.594 - ///\note d.run(s) is just a shortcut of the following code.
2.595 - ///\code
2.596 - /// d.init();
2.597 - /// d.addSource(s);
2.598 - /// d.start();
2.599 - ///\endcode
2.600 - void run(Node s) {
2.601 - init();
2.602 - addSource(s);
2.603 - start();
2.604 - }
2.605 -
2.606 - ///Finds the shortest path between \c s and \c t.
2.607 -
2.608 - ///Finds the shortest path between \c s and \c t.
2.609 - ///
2.610 - ///\return The length of the shortest s---t path if there exists one,
2.611 - ///0 otherwise.
2.612 - ///\note Apart from the return value, d.run(s) is
2.613 - ///just a shortcut of the following code.
2.614 - ///\code
2.615 - /// d.init();
2.616 - /// d.addSource(s);
2.617 - /// d.start(t);
2.618 - ///\endcode
2.619 - Value run(Node s,Node t) {
2.620 - init();
2.621 - addSource(s);
2.622 - start(t);
2.623 - return (*_pred)[t]==INVALID?0:(*_dist)[t];
2.624 - }
2.625 -
2.626 - ///@}
2.627 -
2.628 - ///\name Query Functions
2.629 - ///The result of the %Dijkstra algorithm can be obtained using these
2.630 - ///functions.\n
2.631 - ///Before the use of these functions,
2.632 - ///either run() or start() must be called.
2.633 -
2.634 - ///@{
2.635 -
2.636 - ///The distance of a node from the root.
2.637 -
2.638 - ///Returns the distance of a node from the root.
2.639 - ///\pre \ref run() must be called before using this function.
2.640 - ///\warning If node \c v in unreachable from the root the return value
2.641 - ///of this funcion is undefined.
2.642 - Value dist(Node v) const { return (*_dist)[v]; }
2.643 -
2.644 - ///Returns the 'previous edge' of the shortest path tree.
2.645 -
2.646 - ///For a node \c v it returns the 'previous edge' of the shortest path tree,
2.647 - ///i.e. it returns the last edge of a shortest path from the root to \c
2.648 - ///v. It is \ref INVALID
2.649 - ///if \c v is unreachable from the root or if \c v=s. The
2.650 - ///shortest path tree used here is equal to the shortest path tree used in
2.651 - ///\ref predNode(Node v). \pre \ref run() must be called before using
2.652 - ///this function.
2.653 - ///\todo predEdge could be a better name.
2.654 - Edge pred(Node v) const { return (*_pred)[v]; }
2.655 -
2.656 - ///Returns the 'previous node' of the shortest path tree.
2.657 -
2.658 - ///For a node \c v it returns the 'previous node' of the shortest path tree,
2.659 - ///i.e. it returns the last but one node from a shortest path from the
2.660 - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
2.661 - ///\c v=s. The shortest path tree used here is equal to the shortest path
2.662 - ///tree used in \ref pred(Node v). \pre \ref run() must be called before
2.663 - ///using this function.
2.664 - Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
2.665 - G->source((*_pred)[v]); }
2.666 -
2.667 - ///Returns a reference to the NodeMap of distances.
2.668 -
2.669 - ///Returns a reference to the NodeMap of distances. \pre \ref run() must
2.670 - ///be called before using this function.
2.671 - const DistMap &distMap() const { return *_dist;}
2.672 -
2.673 - ///Returns a reference to the shortest path tree map.
2.674 -
2.675 - ///Returns a reference to the NodeMap of the edges of the
2.676 - ///shortest path tree.
2.677 - ///\pre \ref run() must be called before using this function.
2.678 - const PredMap &predMap() const { return *_pred;}
2.679 -
2.680 - ///Returns a reference to the map of nodes of shortest paths.
2.681 -
2.682 - ///Returns a reference to the NodeMap of the last but one nodes of the
2.683 - ///shortest path tree.
2.684 - ///\pre \ref run() must be called before using this function.
2.685 - const PredNodeMap &predNodeMap() const { return *_predNode;}
2.686 -
2.687 - ///Checks if a node is reachable from the root.
2.688 -
2.689 - ///Returns \c true if \c v is reachable from the root.
2.690 - ///\warning If the algorithm is started from multiple nodes,
2.691 - ///this function may give false result for the source nodes.
2.692 - ///\pre \ref run() must be called before using this function.
2.693 - ///
2.694 - bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
2.695 -
2.696 - ///@}
2.697 - };
2.698 -
2.699 - /// Default traits used by \ref DijkstraWizard
2.700 -
2.701 - /// To make it easier to use Dijkstra algorithm we have created a wizard class.
2.702 - /// This \ref DijkstraWizard class needs default traits, as well as the \ref Dijkstra class.
2.703 - /// The \ref DijkstraWizardBase is a class to be the default traits of the
2.704 - /// \ref DijkstraWizard class.
2.705 - template<class GR,class LM>
2.706 - class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
2.707 - {
2.708 -
2.709 - typedef DijkstraDefaultTraits<GR,LM> Base;
2.710 - protected:
2.711 - /// Pointer to the underlying graph.
2.712 - void *_g;
2.713 - /// Pointer to the length map
2.714 - void *_length;
2.715 - ///Pointer to the map of predecessors edges.
2.716 - void *_pred;
2.717 - ///Pointer to the map of predecessors nodes.
2.718 - void *_predNode;
2.719 - ///Pointer to the map of distances.
2.720 - void *_dist;
2.721 - ///Pointer to the source node.
2.722 - void *_source;
2.723 -
2.724 - /// Type of the nodes in the graph.
2.725 - typedef typename Base::Graph::Node Node;
2.726 -
2.727 - public:
2.728 - /// Constructor.
2.729 -
2.730 - /// This constructor does not require parameters, therefore it initiates
2.731 - /// all of the attributes to default values (0, INVALID).
2.732 - DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
2.733 - _dist(0), _source(INVALID) {}
2.734 -
2.735 - /// Constructor.
2.736 -
2.737 - /// This constructor requires some parameters, listed in the parameters list.
2.738 - /// Others are initiated to 0.
2.739 - /// \param g is the initial value of \ref _g
2.740 - /// \param l is the initial value of \ref _length
2.741 - /// \param s is the initial value of \ref _source
2.742 - DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
2.743 - _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
2.744 - _dist(0), _source((void *)&s) {}
2.745 -
2.746 - };
2.747 -
2.748 - /// A class to make easier the usage of Dijkstra algorithm
2.749 -
2.750 - /// This class is created to make it easier to use Dijkstra algorithm.
2.751 - /// It uses the functions and features of the plain \ref Dijkstra,
2.752 - /// but it is much more simple to use it.
2.753 - ///
2.754 - /// Simplicity means that the way to change the types defined
2.755 - /// in the traits class is based on functions that returns the new class
2.756 - /// and not on templatable built-in classes. When using the plain \ref Dijkstra
2.757 - /// the new class with the modified type comes from the original class by using the ::
2.758 - /// operator. In the case of \ref DijkstraWizard only a function have to be called and it will
2.759 - /// return the needed class.
2.760 - ///
2.761 - /// It does not have own \ref run method. When its \ref run method is called
2.762 - /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
2.763 - /// method of it.
2.764 - template<class TR>
2.765 - class DijkstraWizard : public TR
2.766 - {
2.767 - typedef TR Base;
2.768 -
2.769 - ///The type of the underlying graph.
2.770 - typedef typename TR::Graph Graph;
2.771 - //\e
2.772 - typedef typename Graph::Node Node;
2.773 - //\e
2.774 - typedef typename Graph::NodeIt NodeIt;
2.775 - //\e
2.776 - typedef typename Graph::Edge Edge;
2.777 - //\e
2.778 - typedef typename Graph::OutEdgeIt OutEdgeIt;
2.779 -
2.780 - ///The type of the map that stores the edge lengths.
2.781 - typedef typename TR::LengthMap LengthMap;
2.782 - ///The type of the length of the edges.
2.783 - typedef typename LengthMap::Value Value;
2.784 - ///\brief The type of the map that stores the last
2.785 - ///edges of the shortest paths.
2.786 - typedef typename TR::PredMap PredMap;
2.787 - ///\brief The type of the map that stores the last but one
2.788 - ///nodes of the shortest paths.
2.789 - typedef typename TR::PredNodeMap PredNodeMap;
2.790 - ///The type of the map that stores the dists of the nodes.
2.791 - typedef typename TR::DistMap DistMap;
2.792 -
2.793 - ///The heap type used by the dijkstra algorithm.
2.794 - typedef typename TR::Heap Heap;
2.795 -public:
2.796 - /// Constructor.
2.797 - DijkstraWizard() : TR() {}
2.798 -
2.799 - /// Constructor that requires parameters.
2.800 -
2.801 - /// Constructor that requires parameters.
2.802 - /// These parameters will be the default values for the traits class.
2.803 - DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
2.804 - TR(g,l,s) {}
2.805 -
2.806 - ///Copy constructor
2.807 - DijkstraWizard(const TR &b) : TR(b) {}
2.808 -
2.809 - ~DijkstraWizard() {}
2.810 -
2.811 - ///Runs Dijkstra algorithm from a given node.
2.812 -
2.813 - ///Runs Dijkstra algorithm from a given node.
2.814 - ///The node can be given by the \ref source function.
2.815 - void run()
2.816 - {
2.817 - if(_source==0) throw UninitializedParameter();
2.818 - Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
2.819 - if(_pred) Dij.predMap(*(PredMap*)_pred);
2.820 - if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
2.821 - if(_dist) Dij.distMap(*(DistMap*)_dist);
2.822 - Dij.run(*(Node*)_source);
2.823 - }
2.824 -
2.825 - ///Runs Dijkstra algorithm from the given node.
2.826 -
2.827 - ///Runs Dijkstra algorithm from the given node.
2.828 - ///\param s is the given source.
2.829 - void run(Node s)
2.830 - {
2.831 - _source=(void *)&s;
2.832 - run();
2.833 - }
2.834 -
2.835 - template<class T>
2.836 - struct DefPredMapBase : public Base {
2.837 - typedef T PredMap;
2.838 - static PredMap *createPredMap(const Graph &G) { return 0; };
2.839 - DefPredMapBase(const Base &b) : Base(b) {}
2.840 - };
2.841 -
2.842 - /// \ref named-templ-param "Named parameter" function for setting PredMap type
2.843 -
2.844 - /// \ref named-templ-param "Named parameter" function for setting PredMap type
2.845 - ///
2.846 - template<class T>
2.847 - DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
2.848 - {
2.849 - _pred=(void *)&t;
2.850 - return DijkstraWizard<DefPredMapBase<T> >(*this);
2.851 - }
2.852 -
2.853 -
2.854 - template<class T>
2.855 - struct DefPredNodeMapBase : public Base {
2.856 - typedef T PredNodeMap;
2.857 - static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
2.858 - DefPredNodeMapBase(const Base &b) : Base(b) {}
2.859 - };
2.860 -
2.861 - /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
2.862 -
2.863 - /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
2.864 - ///
2.865 - template<class T>
2.866 - DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
2.867 - {
2.868 - _predNode=(void *)&t;
2.869 - return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
2.870 - }
2.871 -
2.872 - template<class T>
2.873 - struct DefDistMapBase : public Base {
2.874 - typedef T DistMap;
2.875 - static DistMap *createDistMap(const Graph &G) { return 0; };
2.876 - DefDistMapBase(const Base &b) : Base(b) {}
2.877 - };
2.878 -
2.879 - /// \ref named-templ-param "Named parameter" function for setting DistMap type
2.880 -
2.881 - /// \ref named-templ-param "Named parameter" function for setting DistMap type
2.882 - ///
2.883 - template<class T>
2.884 - DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
2.885 - {
2.886 - _dist=(void *)&t;
2.887 - return DijkstraWizard<DefDistMapBase<T> >(*this);
2.888 - }
2.889 -
2.890 - /// Sets the source node, from which the Dijkstra algorithm runs.
2.891 -
2.892 - /// Sets the source node, from which the Dijkstra algorithm runs.
2.893 - /// \param s is the source node.
2.894 - DijkstraWizard<TR> &source(Node s)
2.895 - {
2.896 - source=(void *)&s;
2.897 - return *this;
2.898 - }
2.899 -
2.900 - };
2.901 -
2.902 - ///\e
2.903 -
2.904 - ///\todo Please document...
2.905 - ///
2.906 - template<class GR, class LM>
2.907 - DijkstraWizard<DijkstraWizardBase<GR,LM> >
2.908 - dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
2.909 - {
2.910 - return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
2.911 - }
2.912 -
2.913 -/// @}
2.914 -
2.915 -} //END OF NAMESPACE LEMON
2.916 -
2.917 -#endif
2.918 -