diff -r d8475431bbbb -r 8e85e6bbefdf src/lemon/dijkstra.h --- a/src/lemon/dijkstra.h Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1074 +0,0 @@ -/* -*- C++ -*- - * src/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 -