# HG changeset patch # User alpar # Date 1107720870 0 # Node ID ab5c81fcc31a89adf765573dd122674565941790 # Parent 425731cb66de954f711bc1ac6b1e701addf6bebc Revised dijkstra.h with several new features added. diff -r 425731cb66de -r ab5c81fcc31a src/lemon/dijkstra.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/dijkstra.h Sun Feb 06 20:14:30 2005 +0000 @@ -0,0 +1,915 @@ +/* -*- C++ -*- + * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, 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. + +#include +#include +#include +#include +#include + +namespace lemon { + + +/// \addtogroup flowalgs +/// @{ + + ///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 reached. + + ///The type of the map that stores whether a nodes is reached. + ///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::reached() should read this. + ///\todo named parameter to set this type, function to read and write. + typedef NullMap ReachedMap; + ///Instantiates a ReachedMap. + + ///This function instantiates a \ref ReachedMap. + ///\param G is the graph, to which we would like to define the \ref ReachedMap + static ReachedMap *createReachedMap(const GR &G) + { + return new ReachedMap(); + } + ///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. + + ///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::Dijsktra::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 reached. + typedef typename TR::ReachedMap ReachedMap; + ///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 reached status of the nodes. + ReachedMap *_reached; + ///Indicates if \ref _reached is locally allocated (\c true) or not. + bool local_reached; + + ///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(!_reached) { + local_reached = true; + _reached = Traits::createReachedMap(*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 DefReachedMapTraits : public Traits { + typedef T ReachedMap; + static ReachedMap *createReachedMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting ReachedMap type + + ///\ref named-templ-param "Named parameter" for setting ReachedMap type + /// + template + class DefReachedMap : public Dijkstra< Graph, + LengthMap, + DefReachedMapTraits > { }; + + struct DefGraphReachedMapTraits : public Traits { + typedef typename Graph::NodeMap ReachedMap; + static ReachedMap *createReachedMap(const Graph &G) + { + return new ReachedMap(G); + } + }; + ///\brief \ref named-templ-param "Named parameter" + ///for setting the ReachedMap type to be Graph::NodeMap. + /// + ///\ref named-templ-param "Named parameter" + ///for setting the ReachedMap type to be Graph::NodeMap. + ///If you don't set it explicitely, it will be automatically allocated. + template + class DefReachedMapToBeDefaultMap : + public Dijkstra< Graph, + LengthMap, + DefGraphReachedMapTraits> { }; + + ///@} + + + 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), + _reached(NULL), local_reached(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_reached) delete _reached; + } + + ///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) + { + _reached->set(v,true); + _dist->set(v, dst); + _predNode->set(v,G->source((*_pred)[v])); + } + + public: + ///\name Excetution control + ///The simplest way to execute the algorithm is to use + ///\ref run(). + ///\n + ///It 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. + void init() + { + create_maps(); + + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { + _pred->set(u,INVALID); + _predNode->set(u,INVALID); + ///\todo *_reached is not set to false. + _heap_map.set(u,Heap::PRE_HEAP); + } + } + + ///Adds a new source node. + + ///Adds a new source node the the priority heap. + ///It checks if the node has already been added to the heap. + /// + ///The optional second parameter is the initial distance of the node. + /// + ///\todo Do we really want to check it? + void addSource(Node s,Value dst=0) + { + source = s; + if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); + } + + void processNode() + { + 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; + } + } + } + + ///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() ) processNode(); + } + + ///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 ) processNode(); + if ( _heap.top()==dest ) finalizeNodeData(_heap.top()); + } + + ///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 NM &nm) + { + while ( !_heap.empty() && !mn[_heap.top()] ) processNode(); + if ( !_heap.empty() ) finalizeNodeData(_heap.top()); + } + + ///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. + + ///@{ + + ///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 If the algorithm is started from multiple nodes, + ///this function may give false result for the source nodes. + ///\pre \ref run() must be called before using this function. + /// + bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; } + + ///@} + }; + + /// 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. + template + class DijkstraWizardBase : public DijkstraDefaultTraits + { + + typedef DijkstraDefaultTraits Base; + protected: + /// 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. + void *_source; + + /// Type of the nodes in the graph. + typedef typename Base::Graph::Node Node; + + 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((void *)&s) {} + + }; + + /// A class to make easier the usage of Dijkstra algorithm + + /// 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 more simple 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(_source==0) throw UninitializedParameter(); + Dijkstra Dij(*(Graph*)_g,*(LengthMap*)_length); + if(_pred) Dij.predMap(*(PredMap*)_pred); + if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode); + if(_dist) Dij.distMap(*(DistMap*)_dist); + Dij.run(*(Node*)_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) + { + _source=(void *)&s; + run(); + } + + template + struct DefPredMapBase : public Base { + typedef T PredMap; + static PredMap *createPredMap(const Graph &G) { return 0; }; + DefPredMapBase(const Base &b) : Base(b) {} + }; + + /// \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) + { + _pred=(void *)&t; + return DijkstraWizard >(*this); + } + + + template + struct DefPredNodeMapBase : public Base { + typedef T PredNodeMap; + static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; + DefPredNodeMapBase(const Base &b) : Base(b) {} + }; + + /// \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) + { + _predNode=(void *)&t; + return DijkstraWizard >(*this); + } + + template + struct DefDistMapBase : public Base { + typedef T DistMap; + static DistMap *createDistMap(const Graph &G) { return 0; }; + DefDistMapBase(const Base &b) : Base(b) {} + }; + + /// \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) + { + _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) + { + source=(void *)&s; + return *this; + } + + }; + + ///\e + + ///\todo Please document... + /// + template + DijkstraWizard > + dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID) + { + return DijkstraWizard >(g,l,s); + } + +/// @} + +} //END OF NAMESPACE LEMON + +#endif + diff -r 425731cb66de -r ab5c81fcc31a src/work/alpar/dijkstra.h --- a/src/work/alpar/dijkstra.h Sun Feb 06 20:08:25 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,915 +0,0 @@ -/* -*- C++ -*- - * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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. - -#include -#include -#include -#include -#include - -namespace lemon { - - -/// \addtogroup flowalgs -/// @{ - - ///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 reached. - - ///The type of the map that stores whether a nodes is reached. - ///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::reached() should read this. - ///\todo named parameter to set this type, function to read and write. - typedef NullMap ReachedMap; - ///Instantiates a ReachedMap. - - ///This function instantiates a \ref ReachedMap. - ///\param G is the graph, to which we would like to define the \ref ReachedMap - static ReachedMap *createReachedMap(const GR &G) - { - return new ReachedMap(); - } - ///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. - - ///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::Dijsktra::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 reached. - typedef typename TR::ReachedMap ReachedMap; - ///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 reached status of the nodes. - ReachedMap *_reached; - ///Indicates if \ref _reached is locally allocated (\c true) or not. - bool local_reached; - - ///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(!_reached) { - local_reached = true; - _reached = Traits::createReachedMap(*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 DefReachedMapTraits : public Traits { - typedef T ReachedMap; - static ReachedMap *createReachedMap(const Graph &G) - { - throw UninitializedParameter(); - } - }; - ///\ref named-templ-param "Named parameter" for setting ReachedMap type - - ///\ref named-templ-param "Named parameter" for setting ReachedMap type - /// - template - class DefReachedMap : public Dijkstra< Graph, - LengthMap, - DefReachedMapTraits > { }; - - struct DefGraphReachedMapTraits : public Traits { - typedef typename Graph::NodeMap ReachedMap; - static ReachedMap *createReachedMap(const Graph &G) - { - return new ReachedMap(G); - } - }; - ///\brief \ref named-templ-param "Named parameter" - ///for setting the ReachedMap type to be Graph::NodeMap. - /// - ///\ref named-templ-param "Named parameter" - ///for setting the ReachedMap type to be Graph::NodeMap. - ///If you don't set it explicitely, it will be automatically allocated. - template - class DefReachedMapToBeDefaultMap : - public Dijkstra< Graph, - LengthMap, - DefGraphReachedMapTraits> { }; - - ///@} - - - 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), - _reached(NULL), local_reached(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_reached) delete _reached; - } - - ///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) - { - _reached->set(v,true); - _dist->set(v, dst); - _predNode->set(v,G->source((*_pred)[v])); - } - - public: - ///\name Excetution control - ///The simplest way to execute the algorithm is to use - ///\ref run(). - ///\n - ///It 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. - void init() - { - create_maps(); - - for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { - _pred->set(u,INVALID); - _predNode->set(u,INVALID); - ///\todo *_reached is not set to false. - _heap_map.set(u,Heap::PRE_HEAP); - } - } - - ///Adds a new source node. - - ///Adds a new source node the the priority heap. - ///It checks if the node has already been added to the heap. - /// - ///The optional second parameter is the initial distance of the node. - /// - ///\todo Do we really want to check it? - void addSource(Node s,Value dst=0) - { - source = s; - if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); - } - - void processNode() - { - 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; - } - } - } - - ///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() ) processNode(); - } - - ///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 ) processNode(); - if ( _heap.top()==dest ) finalizeNodeData(_heap.top()); - } - - ///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 NM &nm) - { - while ( !_heap.empty() && !mn[_heap.top()] ) processNode(); - if ( !_heap.empty() ) finalizeNodeData(_heap.top()); - } - - ///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. - - ///@{ - - ///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 If the algorithm is started from multiple nodes, - ///this function may give false result for the source nodes. - ///\pre \ref run() must be called before using this function. - /// - bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; } - - ///@} - }; - - /// 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. - template - class DijkstraWizardBase : public DijkstraDefaultTraits - { - - typedef DijkstraDefaultTraits Base; - protected: - /// 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. - void *_source; - - /// Type of the nodes in the graph. - typedef typename Base::Graph::Node Node; - - 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((void *)&s) {} - - }; - - /// A class to make easier the usage of Dijkstra algorithm - - /// 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 more simple 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(_source==0) throw UninitializedParameter(); - Dijkstra Dij(*(Graph*)_g,*(LengthMap*)_length); - if(_pred) Dij.predMap(*(PredMap*)_pred); - if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode); - if(_dist) Dij.distMap(*(DistMap*)_dist); - Dij.run(*(Node*)_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) - { - _source=(void *)&s; - run(); - } - - template - struct DefPredMapBase : public Base { - typedef T PredMap; - static PredMap *createPredMap(const Graph &G) { return 0; }; - DefPredMapBase(const Base &b) : Base(b) {} - }; - - /// \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) - { - _pred=(void *)&t; - return DijkstraWizard >(*this); - } - - - template - struct DefPredNodeMapBase : public Base { - typedef T PredNodeMap; - static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; - DefPredNodeMapBase(const Base &b) : Base(b) {} - }; - - /// \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) - { - _predNode=(void *)&t; - return DijkstraWizard >(*this); - } - - template - struct DefDistMapBase : public Base { - typedef T DistMap; - static DistMap *createDistMap(const Graph &G) { return 0; }; - DefDistMapBase(const Base &b) : Base(b) {} - }; - - /// \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) - { - _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) - { - source=(void *)&s; - return *this; - } - - }; - - ///\e - - ///\todo Please document... - /// - template - DijkstraWizard > - dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID) - { - return DijkstraWizard >(g,l,s); - } - -/// @} - -} //END OF NAMESPACE LEMON - -#endif -