diff -r d8475431bbbb -r 8e85e6bbefdf lemon/dijkstra.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/dijkstra.h Mon May 23 04:48:14 2005 +0000 @@ -0,0 +1,1074 @@ +/* -*- C++ -*- + * lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_DIJKSTRA_H +#define LEMON_DIJKSTRA_H + +///\ingroup flowalgs +///\file +///\brief Dijkstra algorithm. +/// +///\todo getPath() should be implemented! (also for BFS and DFS) + +#include +#include +#include +#include +#include + +namespace lemon { + + + + ///Default traits class of Dijkstra class. + + ///Default traits class of Dijkstra class. + ///\param GR Graph type. + ///\param LM Type of length map. + template + struct DijkstraDefaultTraits + { + ///The graph type the algorithm runs on. + typedef GR Graph; + ///The type of the map that stores the edge lengths. + + ///The type of the map that stores the edge lengths. + ///It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef LM LengthMap; + //The type of the length of the edges. + typedef typename LM::Value Value; + ///The heap type used by Dijkstra algorithm. + + ///The heap type used by Dijkstra algorithm. + /// + ///\sa BinHeap + ///\sa Dijkstra + typedef BinHeap, + std::less > Heap; + + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + /// + ///The type of the map that stores the last + ///edges of the shortest paths. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap PredMap; + ///Instantiates a PredMap. + + ///This function instantiates a \ref PredMap. + ///\param G is the graph, to which we would like to define the PredMap. + ///\todo The graph alone may be insufficient for the initialization + static PredMap *createPredMap(const GR &G) + { + return new PredMap(G); + } +// ///\brief The type of the map that stores the last but one +// ///nodes of the shortest paths. +// /// +// ///The type of the map that stores the last but one +// ///nodes of the shortest paths. +// ///It must meet the \ref concept::WriteMap "WriteMap" concept. +// /// +// typedef NullMap PredNodeMap; +// ///Instantiates a PredNodeMap. + +// ///This function instantiates a \ref PredNodeMap. +// ///\param G is the graph, to which +// ///we would like to define the \ref PredNodeMap +// static PredNodeMap *createPredNodeMap(const GR &G) +// { +// return new PredNodeMap(); +// } + + ///The type of the map that stores whether a nodes is processed. + + ///The type of the map that stores whether a nodes is processed. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///By default it is a NullMap. + ///\todo If it is set to a real map, + ///Dijkstra::processed() should read this. + ///\todo named parameter to set this type, function to read and write. + typedef NullMap ProcessedMap; + ///Instantiates a ProcessedMap. + + ///This function instantiates a \ref ProcessedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ProcessedMap + static ProcessedMap *createProcessedMap(const GR &) + { + return new ProcessedMap(); + } + ///The type of the map that stores the dists of the nodes. + + ///The type of the map that stores the dists of the nodes. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap DistMap; + ///Instantiates a DistMap. + + ///This function instantiates a \ref DistMap. + ///\param G is the graph, to which we would like to define the \ref DistMap + static DistMap *createDistMap(const GR &G) + { + return new DistMap(G); + } + }; + + ///%Dijkstra algorithm class. + + /// \ingroup flowalgs + ///This class provides an efficient implementation of %Dijkstra algorithm. + ///The edge lengths are passed to the algorithm using a + ///\ref concept::ReadMap "ReadMap", + ///so it is easy to change it to any kind of length. + /// + ///The type of the length is determined by the + ///\ref concept::ReadMap::Value "Value" of the length map. + /// + ///It is also possible to change the underlying priority heap. + /// + ///\param GR The graph type the algorithm runs on. The default value + ///is \ref ListGraph. The value of GR is not used directly by + ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits. + ///\param LM This read-only EdgeMap determines the lengths of the + ///edges. It is read once for each edge, so the map may involve in + ///relatively time consuming process to compute the edge length if + ///it is necessary. The default map type is \ref + ///concept::StaticGraph::EdgeMap "Graph::EdgeMap". The value + ///of LM is not used directly by Dijkstra, it is only passed to \ref + ///DijkstraDefaultTraits. \param TR Traits class to set + ///various data types used by the algorithm. The default traits + ///class is \ref DijkstraDefaultTraits + ///"DijkstraDefaultTraits". See \ref + ///DijkstraDefaultTraits for the documentation of a Dijkstra traits + ///class. + /// + ///\author Jacint Szabo and Alpar Juttner + ///\todo A compare object would be nice. + +#ifdef DOXYGEN + template +#else + template , + typename TR=DijkstraDefaultTraits > +#endif + class Dijkstra { + public: + /** + * \brief \ref Exception for uninitialized parameters. + * + * This error represents problems in the initialization + * of the parameters of the algorithms. + */ + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* exceptionName() const { + return "lemon::Dijkstra::UninitializedParameter"; + } + }; + + typedef TR Traits; + ///The type of the underlying graph. + typedef typename TR::Graph Graph; + ///\e + typedef typename Graph::Node Node; + ///\e + typedef typename Graph::NodeIt NodeIt; + ///\e + typedef typename Graph::Edge Edge; + ///\e + typedef typename Graph::OutEdgeIt OutEdgeIt; + + ///The type of the length of the edges. + typedef typename TR::LengthMap::Value Value; + ///The type of the map that stores the edge lengths. + typedef typename TR::LengthMap LengthMap; + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + typedef typename TR::PredMap PredMap; +// ///\brief The type of the map that stores the last but one +// ///nodes of the shortest paths. +// typedef typename TR::PredNodeMap PredNodeMap; + ///The type of the map indicating if a node is processed. + typedef typename TR::ProcessedMap ProcessedMap; + ///The type of the map that stores the dists of the nodes. + typedef typename TR::DistMap DistMap; + ///The heap type used by the dijkstra algorithm. + typedef typename TR::Heap Heap; + private: + /// Pointer to the underlying graph. + const Graph *G; + /// Pointer to the length map + const LengthMap *length; + ///Pointer to the map of predecessors edges. + PredMap *_pred; + ///Indicates if \ref _pred is locally allocated (\c true) or not. + bool local_pred; +// ///Pointer to the map of predecessors nodes. +// PredNodeMap *_predNode; +// ///Indicates if \ref _predNode is locally allocated (\c true) or not. +// bool local_predNode; + ///Pointer to the map of distances. + DistMap *_dist; + ///Indicates if \ref _dist is locally allocated (\c true) or not. + bool local_dist; + ///Pointer to the map of processed status of the nodes. + ProcessedMap *_processed; + ///Indicates if \ref _processed is locally allocated (\c true) or not. + bool local_processed; + +// ///The source node of the last execution. +// Node source; + + ///Creates the maps if necessary. + + ///\todo Error if \c G or are \c NULL. What about \c length? + ///\todo Better memory allocation (instead of new). + void create_maps() + { + if(!_pred) { + local_pred = true; + _pred = Traits::createPredMap(*G); + } +// if(!_predNode) { +// local_predNode = true; +// _predNode = Traits::createPredNodeMap(*G); +// } + if(!_dist) { + local_dist = true; + _dist = Traits::createDistMap(*G); + } + if(!_processed) { + local_processed = true; + _processed = Traits::createProcessedMap(*G); + } + } + + public : + + ///\name Named template parameters + + ///@{ + + template + struct DefPredMapTraits : public Traits { + typedef T PredMap; + static PredMap *createPredMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting PredMap type + + ///\ref named-templ-param "Named parameter" for setting PredMap type + /// + template + class DefPredMap : public Dijkstra< Graph, + LengthMap, + DefPredMapTraits > { }; + +// template +// struct DefPredNodeMapTraits : public Traits { +// typedef T PredNodeMap; +// static PredNodeMap *createPredNodeMap(const Graph &G) +// { +// throw UninitializedParameter(); +// } +// }; +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type + +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type +// /// +// template +// class DefPredNodeMap : public Dijkstra< Graph, +// LengthMap, +// DefPredNodeMapTraits > { }; + + template + struct DefDistMapTraits : public Traits { + typedef T DistMap; + static DistMap *createDistMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting DistMap type + + ///\ref named-templ-param "Named parameter" for setting DistMap type + /// + template + class DefDistMap : public Dijkstra< Graph, + LengthMap, + DefDistMapTraits > { }; + + template + struct DefProcessedMapTraits : public Traits { + typedef T ProcessedMap; + static ProcessedMap *createProcessedMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type + + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type + /// + template + class DefProcessedMap : public Dijkstra< Graph, + LengthMap, + DefProcessedMapTraits > { }; + + struct DefGraphProcessedMapTraits : public Traits { + typedef typename Graph::template NodeMap ProcessedMap; + static ProcessedMap *createProcessedMap(const Graph &G) + { + return new ProcessedMap(G); + } + }; + ///\brief \ref named-templ-param "Named parameter" + ///for setting the ProcessedMap type to be Graph::NodeMap. + /// + ///\ref named-templ-param "Named parameter" + ///for setting the ProcessedMap type to be Graph::NodeMap. + ///If you don't set it explicitely, it will be automatically allocated. + template + class DefProcessedMapToBeDefaultMap : + public Dijkstra< Graph, + LengthMap, + DefGraphProcessedMapTraits> { }; + + ///@} + + + private: + typename Graph::template NodeMap _heap_map; + Heap _heap; + public: + + ///Constructor. + + ///\param _G the graph the algorithm will run on. + ///\param _length the length map used by the algorithm. + Dijkstra(const Graph& _G, const LengthMap& _length) : + G(&_G), length(&_length), + _pred(NULL), local_pred(false), +// _predNode(NULL), local_predNode(false), + _dist(NULL), local_dist(false), + _processed(NULL), local_processed(false), + _heap_map(*G,-1),_heap(_heap_map) + { } + + ///Destructor. + ~Dijkstra() + { + if(local_pred) delete _pred; +// if(local_predNode) delete _predNode; + if(local_dist) delete _dist; + if(local_processed) delete _processed; + } + + ///Sets the length map. + + ///Sets the length map. + ///\return (*this) + Dijkstra &lengthMap(const LengthMap &m) + { + length = &m; + return *this; + } + + ///Sets the map storing the predecessor edges. + + ///Sets the map storing the predecessor edges. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Dijkstra &predMap(PredMap &m) + { + if(local_pred) { + delete _pred; + local_pred=false; + } + _pred = &m; + return *this; + } + +// ///Sets the map storing the predecessor nodes. + +// ///Sets the map storing the predecessor nodes. +// ///If you don't use this function before calling \ref run(), +// ///it will allocate one. The destuctor deallocates this +// ///automatically allocated map, of course. +// ///\return (*this) +// Dijkstra &predNodeMap(PredNodeMap &m) +// { +// if(local_predNode) { +// delete _predNode; +// local_predNode=false; +// } +// _predNode = &m; +// return *this; +// } + + ///Sets the map storing the distances calculated by the algorithm. + + ///Sets the map storing the distances calculated by the algorithm. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Dijkstra &distMap(DistMap &m) + { + if(local_dist) { + delete _dist; + local_dist=false; + } + _dist = &m; + return *this; + } + + private: + void finalizeNodeData(Node v,Value dst) + { + _processed->set(v,true); + _dist->set(v, dst); +// if((*_pred)[v]!=INVALID) +// _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do? + } + + public: + ///\name Execution control + ///The simplest way to execute the algorithm is to use + ///one of the member functions called \c run(...). + ///\n + ///If you need more control on the execution, + ///first you must call \ref init(), then you can add several source nodes + ///with \ref addSource(). + ///Finally \ref start() will perform the actual path + ///computation. + + ///@{ + + ///Initializes the internal data structures. + + ///Initializes the internal data structures. + /// + ///\todo _heap_map's type could also be in the traits class. + ///\todo The heaps should be able to make themselves empty directly. + void init() + { + create_maps(); + while(!_heap.empty()) _heap.pop(); + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { + _pred->set(u,INVALID); +// _predNode->set(u,INVALID); + _processed->set(u,false); + _heap_map.set(u,Heap::PRE_HEAP); + } + } + + ///Adds a new source node. + + ///Adds a new source node to the priority heap. + /// + ///The optional second parameter is the initial distance of the node. + /// + ///It checks if the node has already been added to the heap and + ///It is pushed to the heap only if either it was not in the heap + ///or the shortest path found till then is longer then \c dst. + void addSource(Node s,Value dst=0) + { +// source = s; + if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); + else if(_heap[s]set(s,INVALID); + } + } + + ///Processes the next node in the priority heap + + ///Processes the next node in the priority heap. + /// + ///\warning The priority heap must not be empty! + void processNextNode() + { + Node v=_heap.top(); + Value oldvalue=_heap[v]; + _heap.pop(); + finalizeNodeData(v,oldvalue); + + for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { + Node w=G->target(e); + switch(_heap.state(w)) { + case Heap::PRE_HEAP: + _heap.push(w,oldvalue+(*length)[e]); + _pred->set(w,e); +// _predNode->set(w,v); + break; + case Heap::IN_HEAP: + if ( oldvalue+(*length)[e] < _heap[w] ) { + _heap.decrease(w, oldvalue+(*length)[e]); + _pred->set(w,e); +// _predNode->set(w,v); + } + break; + case Heap::POST_HEAP: + break; + } + } + } + + ///\brief Returns \c false if there are nodes + ///to be processed in the priority heap + /// + ///Returns \c false if there are nodes + ///to be processed in the priority heap + bool emptyQueue() { return _heap.empty(); } + ///Returns the number of the nodes to be processed in the priority heap + + ///Returns the number of the nodes to be processed in the priority heap + /// + int queueSize() { return _heap.size(); } + + ///Executes the algorithm. + + ///Executes the algorithm. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///This method runs the %Dijkstra algorithm from the root node(s) + ///in order to + ///compute the + ///shortest path to each node. The algorithm computes + ///- The shortest path tree. + ///- The distance of each node from the root(s). + /// + void start() + { + while ( !_heap.empty() ) processNextNode(); + } + + ///Executes the algorithm until \c dest is reached. + + ///Executes the algorithm until \c dest is reached. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///This method runs the %Dijkstra algorithm from the root node(s) + ///in order to + ///compute the + ///shortest path to \c dest. The algorithm computes + ///- The shortest path to \c dest. + ///- The distance of \c dest from the root(s). + /// + void start(Node dest) + { + while ( !_heap.empty() && _heap.top()!=dest ) processNextNode(); + if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio()); + } + + ///Executes the algorithm until a condition is met. + + ///Executes the algorithm until a condition is met. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///\param nm must be a bool (or convertible) node map. The algorithm + ///will stop when it reaches a node \c v with nm[v]==true. + template + void start(const NodeBoolMap &nm) + { + while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode(); + if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio()); + } + + ///Runs %Dijkstra algorithm from node \c s. + + ///This method runs the %Dijkstra algorithm from a root node \c s + ///in order to + ///compute the + ///shortest path to each node. The algorithm computes + ///- The shortest path tree. + ///- The distance of each node from the root. + /// + ///\note d.run(s) is just a shortcut of the following code. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(); + ///\endcode + void run(Node s) { + init(); + addSource(s); + start(); + } + + ///Finds the shortest path between \c s and \c t. + + ///Finds the shortest path between \c s and \c t. + /// + ///\return The length of the shortest s---t path if there exists one, + ///0 otherwise. + ///\note Apart from the return value, d.run(s) is + ///just a shortcut of the following code. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(t); + ///\endcode + Value run(Node s,Node t) { + init(); + addSource(s); + start(t); + return (*_pred)[t]==INVALID?0:(*_dist)[t]; + } + + ///@} + + ///\name Query Functions + ///The result of the %Dijkstra algorithm can be obtained using these + ///functions.\n + ///Before the use of these functions, + ///either run() or start() must be called. + + ///@{ + + ///Copies the shortest path to \c t into \c p + + ///This function copies the shortest path to \c t into \c p. + ///If it \c \t is a source itself or unreachable, then it does not + ///alter \c p. + ///\todo Is it the right way to handle unreachable nodes? + ///\return Returns \c true if a path to \c t was actually copied to \c p, + ///\c false otherwise. + ///\sa DirPath + template + bool getPath(P &p,Node t) + { + if(reached(t)) { + p.clear(); + typename P::Builder b(p); + for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) + b.pushFront(pred(t)); + b.commit(); + return true; + } + return false; + } + + ///The distance of a node from the root. + + ///Returns the distance of a node from the root. + ///\pre \ref run() must be called before using this function. + ///\warning If node \c v in unreachable from the root the return value + ///of this funcion is undefined. + Value dist(Node v) const { return (*_dist)[v]; } + + ///Returns the 'previous edge' of the shortest path tree. + + ///For a node \c v it returns the 'previous edge' of the shortest path tree, + ///i.e. it returns the last edge of a shortest path from the root to \c + ///v. It is \ref INVALID + ///if \c v is unreachable from the root or if \c v=s. The + ///shortest path tree used here is equal to the shortest path tree used in + ///\ref predNode(Node v). \pre \ref run() must be called before using + ///this function. + ///\todo predEdge could be a better name. + Edge pred(Node v) const { return (*_pred)[v]; } + + ///Returns the 'previous node' of the shortest path tree. + + ///For a node \c v it returns the 'previous node' of the shortest path tree, + ///i.e. it returns the last but one node from a shortest path from the + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if + ///\c v=s. The shortest path tree used here is equal to the shortest path + ///tree used in \ref pred(Node v). \pre \ref run() must be called before + ///using this function. + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: + G->source((*_pred)[v]); } + + ///Returns a reference to the NodeMap of distances. + + ///Returns a reference to the NodeMap of distances. \pre \ref run() must + ///be called before using this function. + const DistMap &distMap() const { return *_dist;} + + ///Returns a reference to the shortest path tree map. + + ///Returns a reference to the NodeMap of the edges of the + ///shortest path tree. + ///\pre \ref run() must be called before using this function. + const PredMap &predMap() const { return *_pred;} + +// ///Returns a reference to the map of nodes of shortest paths. + +// ///Returns a reference to the NodeMap of the last but one nodes of the +// ///shortest path tree. +// ///\pre \ref run() must be called before using this function. +// const PredNodeMap &predNodeMap() const { return *_predNode;} + + ///Checks if a node is reachable from the root. + + ///Returns \c true if \c v is reachable from the root. + ///\warning The source nodes are inditated as unreached. + ///\pre \ref run() must be called before using this function. + /// + bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; } + + ///@} + }; + + + + + + ///Default traits class of Dijkstra function. + + ///Default traits class of Dijkstra function. + ///\param GR Graph type. + ///\param LM Type of length map. + template + struct DijkstraWizardDefaultTraits + { + ///The graph type the algorithm runs on. + typedef GR Graph; + ///The type of the map that stores the edge lengths. + + ///The type of the map that stores the edge lengths. + ///It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef LM LengthMap; + //The type of the length of the edges. + typedef typename LM::Value Value; + ///The heap type used by Dijkstra algorithm. + + ///The heap type used by Dijkstra algorithm. + /// + ///\sa BinHeap + ///\sa Dijkstra + typedef BinHeap, + std::less > Heap; + + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + /// + ///The type of the map that stores the last + ///edges of the shortest paths. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef NullMap PredMap; + ///Instantiates a PredMap. + + ///This function instantiates a \ref PredMap. + ///\param G is the graph, to which we would like to define the PredMap. + ///\todo The graph alone may be insufficient for the initialization + static PredMap *createPredMap(const GR &) + { + return new PredMap(); + } + ///The type of the map that stores whether a nodes is processed. + + ///The type of the map that stores whether a nodes is processed. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///By default it is a NullMap. + ///\todo If it is set to a real map, + ///Dijkstra::processed() should read this. + ///\todo named parameter to set this type, function to read and write. + typedef NullMap ProcessedMap; + ///Instantiates a ProcessedMap. + + ///This function instantiates a \ref ProcessedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ProcessedMap + static ProcessedMap *createProcessedMap(const GR &) + { + return new ProcessedMap(); + } + ///The type of the map that stores the dists of the nodes. + + ///The type of the map that stores the dists of the nodes. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef NullMap DistMap; + ///Instantiates a DistMap. + + ///This function instantiates a \ref DistMap. + ///\param G is the graph, to which we would like to define the \ref DistMap + static DistMap *createDistMap(const GR &) + { + return new DistMap(); + } + }; + + /// Default traits used by \ref DijkstraWizard + + /// To make it easier to use Dijkstra algorithm + ///we have created a wizard class. + /// This \ref DijkstraWizard class needs default traits, + ///as well as the \ref Dijkstra class. + /// The \ref DijkstraWizardBase is a class to be the default traits of the + /// \ref DijkstraWizard class. + /// \todo More named parameters are required... + template + class DijkstraWizardBase : public DijkstraWizardDefaultTraits + { + + typedef DijkstraWizardDefaultTraits Base; + protected: + /// Type of the nodes in the graph. + typedef typename Base::Graph::Node Node; + + /// Pointer to the underlying graph. + void *_g; + /// Pointer to the length map + void *_length; + ///Pointer to the map of predecessors edges. + void *_pred; +// ///Pointer to the map of predecessors nodes. +// void *_predNode; + ///Pointer to the map of distances. + void *_dist; + ///Pointer to the source node. + Node _source; + + public: + /// Constructor. + + /// This constructor does not require parameters, therefore it initiates + /// all of the attributes to default values (0, INVALID). + DijkstraWizardBase() : _g(0), _length(0), _pred(0), +// _predNode(0), + _dist(0), _source(INVALID) {} + + /// Constructor. + + /// This constructor requires some parameters, + /// listed in the parameters list. + /// Others are initiated to 0. + /// \param g is the initial value of \ref _g + /// \param l is the initial value of \ref _length + /// \param s is the initial value of \ref _source + DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : + _g((void *)&g), _length((void *)&l), _pred(0), +// _predNode(0), + _dist(0), _source(s) {} + + }; + + /// A class to make the usage of Dijkstra algorithm easier + + /// This class is created to make it easier to use Dijkstra algorithm. + /// It uses the functions and features of the plain \ref Dijkstra, + /// but it is much simpler to use it. + /// + /// Simplicity means that the way to change the types defined + /// in the traits class is based on functions that returns the new class + /// and not on templatable built-in classes. + /// When using the plain \ref Dijkstra + /// the new class with the modified type comes from + /// the original class by using the :: + /// operator. In the case of \ref DijkstraWizard only + /// a function have to be called and it will + /// return the needed class. + /// + /// It does not have own \ref run method. When its \ref run method is called + /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run + /// method of it. + template + class DijkstraWizard : public TR + { + typedef TR Base; + + ///The type of the underlying graph. + typedef typename TR::Graph Graph; + //\e + typedef typename Graph::Node Node; + //\e + typedef typename Graph::NodeIt NodeIt; + //\e + typedef typename Graph::Edge Edge; + //\e + typedef typename Graph::OutEdgeIt OutEdgeIt; + + ///The type of the map that stores the edge lengths. + typedef typename TR::LengthMap LengthMap; + ///The type of the length of the edges. + typedef typename LengthMap::Value Value; + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + typedef typename TR::PredMap PredMap; +// ///\brief The type of the map that stores the last but one +// ///nodes of the shortest paths. +// typedef typename TR::PredNodeMap PredNodeMap; + ///The type of the map that stores the dists of the nodes. + typedef typename TR::DistMap DistMap; + + ///The heap type used by the dijkstra algorithm. + typedef typename TR::Heap Heap; +public: + /// Constructor. + DijkstraWizard() : TR() {} + + /// Constructor that requires parameters. + + /// Constructor that requires parameters. + /// These parameters will be the default values for the traits class. + DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) : + TR(g,l,s) {} + + ///Copy constructor + DijkstraWizard(const TR &b) : TR(b) {} + + ~DijkstraWizard() {} + + ///Runs Dijkstra algorithm from a given node. + + ///Runs Dijkstra algorithm from a given node. + ///The node can be given by the \ref source function. + void run() + { + if(Base::_source==INVALID) throw UninitializedParameter(); + Dijkstra + dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length); + if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred); +// if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode); + if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist); + dij.run(Base::_source); + } + + ///Runs Dijkstra algorithm from the given node. + + ///Runs Dijkstra algorithm from the given node. + ///\param s is the given source. + void run(Node s) + { + Base::_source=s; + run(); + } + + template + struct DefPredMapBase : public Base { + typedef T PredMap; + static PredMap *createPredMap(const Graph &) { return 0; }; + DefPredMapBase(const TR &b) : TR(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting PredMap type + /// + /// \ref named-templ-param "Named parameter" + ///function for setting PredMap type + /// + template + DijkstraWizard > predMap(const T &t) + { + Base::_pred=(void *)&t; + return DijkstraWizard >(*this); + } + + +// template +// struct DefPredNodeMapBase : public Base { +// typedef T PredNodeMap; +// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; +// DefPredNodeMapBase(const TR &b) : TR(b) {} +// }; + +// ///\brief \ref named-templ-param "Named parameter" +// ///function for setting PredNodeMap type +// /// +// /// \ref named-templ-param "Named parameter" +// ///function for setting PredNodeMap type +// /// +// template +// DijkstraWizard > predNodeMap(const T &t) +// { +// Base::_predNode=(void *)&t; +// return DijkstraWizard >(*this); +// } + + template + struct DefDistMapBase : public Base { + typedef T DistMap; + static DistMap *createDistMap(const Graph &) { return 0; }; + DefDistMapBase(const TR &b) : TR(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting DistMap type + /// + /// \ref named-templ-param "Named parameter" + ///function for setting DistMap type + /// + template + DijkstraWizard > distMap(const T &t) + { + Base::_dist=(void *)&t; + return DijkstraWizard >(*this); + } + + /// Sets the source node, from which the Dijkstra algorithm runs. + + /// Sets the source node, from which the Dijkstra algorithm runs. + /// \param s is the source node. + DijkstraWizard &source(Node s) + { + Base::_source=s; + return *this; + } + + }; + + ///Function type interface for Dijkstra algorithm. + + /// \ingroup flowalgs + ///Function type interface for Dijkstra algorithm. + /// + ///This function also has several + ///\ref named-templ-func-param "named parameters", + ///they are declared as the members of class \ref DijkstraWizard. + ///The following + ///example shows how to use these parameters. + ///\code + /// dijkstra(g,length,source).predMap(preds).run(); + ///\endcode + ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()" + ///to the end of the parameter list. + ///\sa DijkstraWizard + ///\sa Dijkstra + template + DijkstraWizard > + dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID) + { + return DijkstraWizard >(g,l,s); + } + +} //END OF NAMESPACE LEMON + +#endif +