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

equal deleted inserted replaced

-:43b9c3ba6fc9
+:bf1533bdc053
 ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
 ///See \ref DijkstraDefaultTraits for the documentation of
 ///a Dijkstra traits class.
 ///
 ///\author Jacint Szabo and Alpar Juttner
-///\todo We need a typedef-names should be standardized. (-:
+///\todo A compare object would be nice.
 #ifdef DOXYGEN
 template <typename GR,
 	    typename LM,
 	    typename TR>
 bool local_reached;
 ///The source node of the last execution.
 Node source;
-///Initializes the maps.
+///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 init_maps()
+void create_maps()
 {
 if(!_pred) {
 	local_pred = true;
 	_pred = Traits::createPredMap(*G);
 }
 }
 }
 public :
+///\name Named template parameters
+///@{
 template <class T>
 struct DefPredMapTraits : public Traits {
 typedef T PredMap;
-///\todo An exception should be thrown.
-///
 static PredMap *createPredMap(const Graph &G)
 {
 	throw UninitializedParameter();
 }
 };
 					DefPredMapTraits<T> > { };
 template <class T>
 struct DefPredNodeMapTraits : public Traits {
 typedef T PredNodeMap;
-///\todo An exception should be thrown.
-///
 static PredNodeMap *createPredNodeMap(const Graph &G)
 {
 	throw UninitializedParameter();
 }
 };
 					    DefPredNodeMapTraits<T> > { };
 template <class T>
 struct DefDistMapTraits : public Traits {
 typedef T DistMap;
-///\todo An exception should be thrown.
-///
 static DistMap *createDistMap(const Graph &G)
 {
 	throw UninitializedParameter();
 }
 };
 ///
 template <class T>
 class DefDistMap : public Dijkstra< Graph,
 					LengthMap,
 					DefDistMapTraits<T> > { };
+template <class T>
+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 T>
+class DefReachedMap : public Dijkstra< Graph,
+					LengthMap,
+					DefReachedMapTraits<T> > { };
+struct DefGraphReachedMapTraits : public Traits {
+typedef typename Graph::NodeMap<bool> 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<bool>.
+///
+///\ref named-templ-param "Named parameter"
+///for setting the ReachedMap type to be Graph::NodeMap<bool>.
+///If you don't set it explicitely, it will be automatically allocated.
+template <class T>
+class DefReachedMapToBeDefaultMap :
+public Dijkstra< Graph,
+		       LengthMap,
+		       DefGraphReachedMapTraits> { };
+///@}
+private:
+typename Graph::template NodeMap<int> _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),
 pred_node(NULL), local_pred_node(false),
 distance(NULL), local_distance(false),
-_reached(NULL), local_reached(false)
+_reached(NULL), local_reached(false),
+_heap_map(*G,-1),_heap(_heap_map)
 { }
 ///Destructor.
 ~Dijkstra()
 {
 	local_distance=false;
 }
 distance = &m;
 return *this;
 }
-///Runs %Dijkstra algorithm from node \c s.
+///\name Excetution control
+///The simplest way to execute the algorithm is to use
-///This method runs the %Dijkstra algorithm from a root node \c s
+///\ref run().
-///in order to
+///\n
-///compute the
+///It you need more control on the execution,
-///shortest path to each node. The algorithm computes
+///first you must call \ref init(), then you can add several source nodes
-///- The shortest path tree.
+///with \ref addSource(). Finally \ref start() will perform the actual path
-///- The distance of each node from the root.
+///computation.
-///\todo heap_map's type could also be in the traits class.
-void run(Node s) {
+///@{
-init_maps();
+///Initializes the internal data structures.
-source = s;
+///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);
 	pred_node->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();
+_reached->set(v,true);
+Value oldvalue=_heap[v];
+_heap.pop();
+distance->set(v, oldvalue);
-typename Graph::template NodeMap<int> heap_map(*G,-1);
+for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
+	Node w=G->target(e);
-Heap heap(heap_map);
+	switch(_heap.state(w)) {
+	case Heap::PRE_HEAP:
-heap.push(s,0);
+	  _heap.push(w,oldvalue+(*length)[e]);
+	  _pred->set(w,e);
-while ( !heap.empty() ) {
+	  pred_node->set(w,v);
+	  break;
-	Node v=heap.top();
+	case Heap::IN_HEAP:
-	_reached->set(v,true);
+	  if ( oldvalue+(*length)[e] < _heap[w] ) {
-	Value oldvalue=heap[v];
+	    _heap.decrease(w, oldvalue+(*length)[e]);
-	heap.pop();
-	distance->set(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);
 	    pred_node->set(w,v);
-	    break;
-	  case Heap::IN_HEAP:
-	    if ( oldvalue+(*length)[e] < heap[w] ) {
-	      heap.decrease(w, oldvalue+(*length)[e]);
-	      _pred->set(w,e);
-	      pred_node->set(w,v);
-	    }
-	    break;
-	  case Heap::POST_HEAP:
-	    break;
 	  }
+	  break;
+	case Heap::POST_HEAP:
+	  break;
 	}
 }
 }
+///Starts the execution of the algorithm.
+///Starts the execution of the algorithm.
+///
+///\pre init() must be called before and at least one node should be added
+///with addSource().
+///
+///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();
+}
+///Starts the execution of the algorithm until \c dest is reached.
+///Starts the execution of the algorithm until \c dest is reached.
+///
+///\pre init() must be called before and at least one node should be added
+///with addSource().
+///
+///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();
+}
+///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();
+}
+///@}
+///\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
 const PredNodeMap &predNodeMap() const { return *pred_node;}
 ///Checks if a node is reachable from the root.
 ///Returns \c true if \c v is reachable from the root.
-///\note The root node is reported to be reached!
+///\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.

changeset 1128	6a347310d4c2
parent 1126	04e1cb315951
child 1130	47ef467ccf70