lemon-0.x: comparison src/lemon/dijkstra.h

equal deleted inserted replaced

-:0b6f35ead62a
+:d9d984fea157
 ///\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
+//     ///\brief The type of the map that stores the last but one
-///nodes of the shortest paths.
+//     ///nodes of the shortest paths.
-///
+//     ///
-///The type of the map that stores the last but one
+//     ///The type of the map that stores the last but one
-///nodes of the shortest paths.
+//     ///nodes of the shortest paths.
-///It must meet the \ref concept::WriteMap "WriteMap" concept.
+//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
-///
+//     ///
-typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
+//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
-///Instantiates a PredNodeMap.
+//     ///Instantiates a PredNodeMap.
-///This function instantiates a \ref PredNodeMap.
+//     ///This function instantiates a \ref PredNodeMap.
-///\param G is the graph, to which
+//     ///\param G is the graph, to which
-///we would like to define the \ref PredNodeMap
+//     ///we would like to define the \ref PredNodeMap
-static PredNodeMap *createPredNodeMap(const GR &G)
+//     static PredNodeMap *createPredNodeMap(const GR &G)
-{
+//     {
-return new PredNodeMap();
+//       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 processed.
-///The type of the map that stores whether a nodes is reached.
+///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::reached() should read this.
+///\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<typename Graph::Node,bool> ReachedMap;
+typedef NullMap<typename Graph::Node,bool> ProcessedMap;
-///Instantiates a ReachedMap.
+///Instantiates a ProcessedMap.
-///This function instantiates a \ref ReachedMap.
+///This function instantiates a \ref ProcessedMap.
 ///\param G is the graph, to which
-///we would like to define the \ref ReachedMap
+///we would like to define the \ref ProcessedMap
-static ReachedMap *createReachedMap(const GR &G)
+static ProcessedMap *createProcessedMap(const GR &G)
 {
-return new ReachedMap();
+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.
 ///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
+///\param GR The graph type the algorithm runs on. The default value
-///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
+///is \ref ListGraph. The value of GR is not used directly by
-///is only passed to \ref DijkstraDefaultTraits.
+///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
-///\param LM This read-only
+///\param LM This read-only EdgeMap determines the lengths of the
-///EdgeMap
+///edges. It is read once for each edge, so the map may involve in
-///determines the
+///relatively time consuming process to compute the edge length if
-///lengths of the edges. It is read once for each edge, so the map
+///it is necessary. The default map type is \ref
-///may involve in relatively time consuming process to compute the edge
+///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
-///length if it is necessary. The default map type is
+///of LM is not used directly by Dijkstra, it is only passed to \ref
-///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
+///DijkstraDefaultTraits.  \param TR Traits class to set
-///The value of LM is not used directly by Dijkstra, it
+///various data types used by the algorithm.  The default traits
-///is only passed to \ref DijkstraDefaultTraits.
+///class is \ref DijkstraDefaultTraits
-///\param TR Traits class to set various data types used by the algorithm.
+///"DijkstraDefaultTraits<GR,LM>".  See \ref
-///The default traits class is
+///DijkstraDefaultTraits for the documentation of a Dijkstra traits
-///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
+///class.
-///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
 * of the parameters of the algorithms.
 */
 class UninitializedParameter : public lemon::UninitializedParameter {
 public:
 virtual const char* exceptionName() const {
-	return "lemon::Dijsktra::UninitializedParameter";
+	return "lemon::Dijkstra::UninitializedParameter";
 }
 };
 typedef TR Traits;
 ///The type of the underlying graph.
 ///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
+//     ///\brief The type of the map that stores the last but one
-///nodes of the shortest paths.
+//     ///nodes of the shortest paths.
-typedef typename TR::PredNodeMap PredNodeMap;
+//     typedef typename TR::PredNodeMap PredNodeMap;
-///The type of the map indicating if a node is reached.
+///The type of the map indicating if a node is processed.
-typedef typename TR::ReachedMap ReachedMap;
+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:
 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.
+//     ///Pointer to the map of predecessors nodes.
-PredNodeMap *_predNode;
+//     PredNodeMap *_predNode;
-///Indicates if \ref _predNode is locally allocated (\c true) or not.
+//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
-bool local_predNode;
+//     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.
+///Pointer to the map of processed status of the nodes.
-ReachedMap *_reached;
+ProcessedMap *_processed;
-///Indicates if \ref _reached is locally allocated (\c true) or not.
+///Indicates if \ref _processed is locally allocated (\c true) or not.
-bool local_reached;
+bool local_processed;
-///The source node of the last execution.
+//     ///The source node of the last execution.
-Node source;
+//     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).
 {
 if(!_pred) {
 	local_pred = true;
 	_pred = Traits::createPredMap(*G);
 }
-if(!_predNode) {
+//       if(!_predNode) {
-	local_predNode = true;
+// 	local_predNode = true;
-	_predNode = Traits::createPredNodeMap(*G);
+// 	_predNode = Traits::createPredNodeMap(*G);
-}
+//       }
 if(!_dist) {
 	local_dist = true;
 	_dist = Traits::createDistMap(*G);
 }
-if(!_reached) {
+if(!_processed) {
-	local_reached = true;
+	local_processed = true;
-	_reached = Traits::createReachedMap(*G);
+	_processed = Traits::createProcessedMap(*G);
 }
 }
 public :
 template <class T>
 class DefPredMap : public Dijkstra< Graph,
 					LengthMap,
 					DefPredMapTraits<T> > { };
-template <class T>
+//     template <class T>
-struct DefPredNodeMapTraits : public Traits {
+//     struct DefPredNodeMapTraits : public Traits {
-typedef T PredNodeMap;
+//       typedef T PredNodeMap;
-static PredNodeMap *createPredNodeMap(const Graph &G)
+//       static PredNodeMap *createPredNodeMap(const Graph &G)
-{
+//       {
-	throw UninitializedParameter();
+// 	throw UninitializedParameter();
-}
+//       }
-};
+//     };
-///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
-///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
-///
+//     ///
-template <class T>
+//     template <class T>
-class DefPredNodeMap : public Dijkstra< Graph,
+//     class DefPredNodeMap : public Dijkstra< Graph,
-					    LengthMap,
+// 					    LengthMap,
-					    DefPredNodeMapTraits<T> > { };
+// 					    DefPredNodeMapTraits<T> > { };
 template <class T>
 struct DefDistMapTraits : public Traits {
 typedef T DistMap;
 static DistMap *createDistMap(const Graph &G)
 class DefDistMap : public Dijkstra< Graph,
 					LengthMap,
 					DefDistMapTraits<T> > { };
 template <class T>
-struct DefReachedMapTraits : public Traits {
+struct DefProcessedMapTraits : public Traits {
-typedef T ReachedMap;
+typedef T ProcessedMap;
-static ReachedMap *createReachedMap(const Graph &G)
+static ProcessedMap *createProcessedMap(const Graph &G)
 {
 	throw UninitializedParameter();
 }
 };
-///\ref named-templ-param "Named parameter" for setting ReachedMap type
+///\ref named-templ-param "Named parameter" for setting ProcessedMap type
-///\ref named-templ-param "Named parameter" for setting ReachedMap type
+///\ref named-templ-param "Named parameter" for setting ProcessedMap type
 ///
 template <class T>
-class DefReachedMap : public Dijkstra< Graph,
+class DefProcessedMap : public Dijkstra< Graph,
 					LengthMap,
-					DefReachedMapTraits<T> > { };
+					DefProcessedMapTraits<T> > { };
-struct DefGraphReachedMapTraits : public Traits {
+struct DefGraphProcessedMapTraits : public Traits {
-typedef typename Graph::template NodeMap<bool> ReachedMap;
+typedef typename Graph::template NodeMap<bool> ProcessedMap;
-static ReachedMap *createReachedMap(const Graph &G)
+static ProcessedMap *createProcessedMap(const Graph &G)
 {
-	return new ReachedMap(G);
+	return new ProcessedMap(G);
 }
 };
 ///\brief \ref named-templ-param "Named parameter"
-///for setting the ReachedMap type to be Graph::NodeMap<bool>.
+///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
 ///
 ///\ref named-templ-param "Named parameter"
-///for setting the ReachedMap type to be Graph::NodeMap<bool>.
+///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
 ///If you don't set it explicitely, it will be automatically allocated.
 template <class T>
-class DefReachedMapToBeDefaultMap :
+class DefProcessedMapToBeDefaultMap :
 public Dijkstra< Graph,
 		       LengthMap,
-		       DefGraphReachedMapTraits> { };
+		       DefGraphProcessedMapTraits> { };
 ///@}
 private:
 ///\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),
+//       _predNode(NULL), local_predNode(false),
 _dist(NULL), local_dist(false),
-_reached(NULL), local_reached(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_predNode) delete _predNode;
 if(local_dist) delete _dist;
-if(local_reached) delete _reached;
+if(local_processed) delete _processed;
 }
 ///Sets the length map.
 ///Sets the length map.
 }
 _pred = &m;
 return *this;
 }
-///Sets the map storing the predecessor nodes.
+//     ///Sets the map storing the predecessor nodes.
-///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(),
+//     ///If you don't use this function before calling \ref run(),
-///it will allocate one. The destuctor deallocates this
+//     ///it will allocate one. The destuctor deallocates this
-///automatically allocated map, of course.
+//     ///automatically allocated map, of course.
-///\return <tt> (*this) </tt>
+//     ///\return <tt> (*this) </tt>
-Dijkstra &predNodeMap(PredNodeMap &m)
+//     Dijkstra &predNodeMap(PredNodeMap &m)
-{
+//     {
-if(local_predNode) {
+//       if(local_predNode) {
-	delete _predNode;
+// 	delete _predNode;
-	local_predNode=false;
+// 	local_predNode=false;
-}
+//       }
-_predNode = &m;
+//       _predNode = &m;
-return *this;
+//       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(),
 }
 private:
 void finalizeNodeData(Node v,Value dst)
 {
-_reached->set(v,true);
+_processed->set(v,true);
 _dist->set(v, dst);
-if((*_pred)[v]!=INVALID) _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
+//       if((*_pred)[v]!=INVALID)
+//       _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
 }
 public:
-///\name Excetution control
+///\name Execution control
 ///The simplest way to execute the algorithm is to use
 ///one of the member functions called \c run(...).
 ///\n
-///It you need more control on the execution,
+///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
+///with \ref addSource().
+///Finally \ref start() will perform the actual path
 ///computation.
 ///@{
 ///Initializes the internal data structures.
 {
 create_maps();
 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 	_pred->set(u,INVALID);
-	_predNode->set(u,INVALID);
+// 	_predNode->set(u,INVALID);
-	///\todo *_reached is not set to false.
+	_processed->set(u,false);
 	_heap_map.set(u,Heap::PRE_HEAP);
 }
 }
 ///Adds a new source 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;
+//       source = s;
 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
 else if(_heap[s]<dst) {
 	_heap.push(s,dst);
 	_pred->set(s,INVALID);
 }
 	  break;
 	}
 }
 }
-///Returns \c false if there are nodes to be processed in the priority heap
+///\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
+///
-///
+///Returns \c false if there are nodes
-bool emptyHeap() { return _heap.empty(); }
+///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 heapSize() { return _heap.size(); }
+int queueSize() { return _heap.size(); }
 ///Executes the algorithm.
 ///Executes the algorithm.
 ///
 ///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 map of nodes of shortest paths.
-///Returns a reference to the NodeMap of the last but one nodes of the
+//     ///Returns a reference to the NodeMap of the last but one nodes of the
-///shortest path tree.
+//     ///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.
-const PredNodeMap &predNodeMap() const { return *_predNode;}
+///
+bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
-///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 class of Dijkstra function.
+///Default traits class of Dijkstra function.
+///\param GR Graph type.
+///\param LM Type of length map.
+template<class GR, class LM>
+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<typename Graph::Node,
+		    typename LM::Value,
+		    typename GR::template NodeMap<int>,
+		    std::less<Value> > 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 <typename GR::Node,typename GR::Edge> 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();
+}
+///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<typename Graph::Node,bool> 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 &G)
+{
+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<typename Graph::Node,typename LM::Value> 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();
+}
+};
 /// 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 GR,class LM>
-class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
+class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
 {
-typedef DijkstraDefaultTraits<GR,LM> Base;
+typedef DijkstraWizardDefaultTraits<GR,LM> 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.
+//     ///Pointer to the map of predecessors nodes.
-void *_predNode;
+//     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),
+DijkstraWizardBase() : _g(0), _length(0), _pred(0),
-		       _dist(0), _source(INVALID) {}
+// 			   _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),
+_g((void *)&g), _length((void *)&l), _pred(0),
-		  _dist(0), _source(s) {}
+//       _predNode(0),
+_dist(0), _source(s) {}
 };
 /// A class to make easier the usage of Dijkstra algorithm
-/// \ingroup flowalgs
 /// 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
 ///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
+//     ///\brief The type of the map that stores the last but one
-///nodes of the shortest paths.
+//     ///nodes of the shortest paths.
-typedef typename TR::PredNodeMap PredNodeMap;
+//     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;
 {
 if(Base::_source==INVALID) throw UninitializedParameter();
 Dijkstra<Graph,LengthMap,TR>
 	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::_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.
 Base::_pred=(void *)&t;
 return DijkstraWizard<DefPredMapBase<T> >(*this);
 }
-template<class T>
+//     template<class T>
-struct DefPredNodeMapBase : public Base {
+//     struct DefPredNodeMapBase : public Base {
-typedef T PredNodeMap;
+//       typedef T PredNodeMap;
-static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
+//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
-DefPredNodeMapBase(const Base &b) : Base(b) {}
+//       DefPredNodeMapBase(const Base &b) : Base(b) {}
-};
+//     };
-///\brief \ref named-templ-param "Named parameter"
+//     ///\brief \ref named-templ-param "Named parameter"
-///function for setting PredNodeMap type
+//     ///function for setting PredNodeMap type
-///
+//     ///
-/// \ref named-templ-param "Named parameter"
+//     /// \ref named-templ-param "Named parameter"
-///function for setting PredNodeMap type
+//     ///function for setting PredNodeMap type
-///
+//     ///
-template<class T>
+//     template<class T>
-DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
+//     DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
-{
+//     {
-Base::_predNode=(void *)&t;
+//       Base::_predNode=(void *)&t;
-return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
+//       return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
-}
+//     }
 template<class T>
 struct DefDistMapBase : public Base {
 typedef T DistMap;
 static DistMap *createDistMap(const Graph &G) { return 0; };
 return *this;
 }
 };
-///\e
+///Function type interface for Dijkstra algorithm.
 /// \ingroup flowalgs
-///\todo Please document...
+///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<class GR, class LM>
 DijkstraWizard<DijkstraWizardBase<GR,LM> >
 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
 {
 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
 }
-/// @}
 } //END OF NAMESPACE LEMON
 #endif

changeset 1219	ce885274b754
parent 1201	cb26a6250401
child 1220	20b26ee5812b