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

equal deleted inserted replaced

-:e46b6c1e45c6
+:40d4323e2fbd
 ///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 cross reference type used by heap.
+/// The cross reference type used by heap.
+/// Usually it is \c Graph::NodeMap<int>.
+typedef typename Graph::template NodeMap<int> HeapCrossRef;
+///Instantiates a HeapCrossRef.
+///This function instantiates a \ref HeapCrossRef.
+/// \param G is the graph, to which we would like to define the
+/// HeapCrossRef.
+/// \todo The graph alone may be insufficient for the initialization
+static HeapCrossRef *createHeapCrossRef(const GR &G)
+{
+return new HeapCrossRef(G);
+}
 ///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;
+static Heap *createHeap(HeapCrossRef& R)
+{
+return new Heap(R);
+}
 ///\brief The type of the map that stores the last
 ///edges of the shortest paths.
 ///
 ///The type of the map that stores the last
 typedef typename TR::PredMap PredMap;
 ///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 cross reference type used for the current heap.
+typedef typename TR::HeapCrossRef HeapCrossRef;
 ///The heap type used by the dijkstra algorithm.
 typedef typename TR::Heap Heap;
 private:
 /// Pointer to the underlying graph.
 const Graph *G;
 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;
+///Pointer to the heap cross references.
+HeapCrossRef *_heap_cross_ref;
+///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
+bool local_heap_cross_ref;
+///Pointer to the heap.
+Heap *_heap;
+///Indicates if \ref _heap is locally allocated (\c true) or not.
+bool local_heap;
 ///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).
 	_dist = Traits::createDistMap(*G);
 }
 if(!_processed) {
 	local_processed = true;
 	_processed = Traits::createProcessedMap(*G);
+}
+if (!_heap_cross_ref) {
+	local_heap_cross_ref = true;
+	_heap_cross_ref = Traits::createHeapCrossRef(*G);
+}
+if (!_heap) {
+	local_heap = true;
+	_heap = Traits::createHeap(*_heap_cross_ref);
 }
 }
 public :
 template <class T>
 struct DefProcessedMapToBeDefaultMap
 : public Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> {
 typedef Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> Create;
 };
+template <class H, class CR>
+struct DefHeapTraits : public Traits {
+typedef CR HeapCrossRef;
+typedef H Heap;
+static HeapCrossRef *createHeapCrossRef(const Graph &G) {
+	return new HeapCrossRef(G);
+}
+static Heap *createHeap(HeapCrossRef &R)
+{
+	return new Heap(R);
+}
+};
+///\ref named-templ-param "Named parameter" for setting heap and cross
+///reference type
+///\ref named-templ-param "Named parameter" for setting heap and cross
+///reference type
+///
+template <class H, class CR = typename Graph::template NodeMap<int> >
+struct DefHeap
+: public Dijkstra< Graph,	LengthMap, DefHeapTraits<H, CR> > {
+typedef Dijkstra< Graph,	LengthMap, DefHeapTraits<H, CR> > Create;
+};
 ///@}
-private:
-typename Graph::template NodeMap<int> _heap_map;
-Heap _heap;
 protected:
 Dijkstra() {}
 public:
 Dijkstra(const Graph& _G, const LengthMap& _length) :
 G(&_G), length(&_length),
 _pred(NULL), local_pred(false),
 _dist(NULL), local_dist(false),
 _processed(NULL), local_processed(false),
-_heap_map(*G,-1),_heap(_heap_map)
+_heap_cross_ref(NULL), local_heap_cross_ref(false),
+_heap(NULL), local_heap(false)
 { }
 ///Destructor.
 ~Dijkstra()
 {
 if(local_pred) delete _pred;
 if(local_dist) delete _dist;
 if(local_processed) delete _processed;
+if(local_heap_cross_ref) delete _heap_cross_ref;
+if(local_heap) delete _heap;
 }
 ///Sets the length map.
 ///Sets the length map.
 ///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();
+_heap->clear();
 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 	_pred->set(u,INVALID);
 	_processed->set(u,false);
-	_heap_map.set(u,Heap::PRE_HEAP);
+	_heap_cross_ref->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)
 {
-if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
+if(_heap->state(s) != Heap::IN_HEAP) {
-else if(_heap[s]<dst) {
+	_heap->push(s,dst);
-	_heap.push(s,dst);
+} else if((*_heap)[s]<dst) {
+	_heap->push(s,dst);
 	_pred->set(s,INVALID);
 }
 }
 ///Processes the next node in the priority heap
 ///\return The processed node.
 ///
 ///\warning The priority heap must not be empty!
 Node processNextNode()
 {
-Node v=_heap.top();
+Node v=_heap->top();
-Value oldvalue=_heap[v];
+Value oldvalue=_heap->prio();
-_heap.pop();
+_heap->pop();
 finalizeNodeData(v,oldvalue);
 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
 	Node w=G->target(e);
-	switch(_heap.state(w)) {
+	switch(_heap->state(w)) {
 	case Heap::PRE_HEAP:
-	  _heap.push(w,oldvalue+(*length)[e]);
+	  _heap->push(w,oldvalue+(*length)[e]);
 	  _pred->set(w,e);
 	  break;
 	case Heap::IN_HEAP:
-	  if ( oldvalue+(*length)[e] < _heap[w] ) {
+	  if ( oldvalue+(*length)[e] < (*_heap)[w] ) {
-	    _heap.decrease(w, oldvalue+(*length)[e]);
+	    _heap->decrease(w, oldvalue+(*length)[e]);
 	    _pred->set(w,e);
 	  }
 	  break;
 	case Heap::POST_HEAP:
 	  break;
 ///
 ///\return The next node to be processed or INVALID if the priority heap
 /// is empty.
 Node nextNode()
 {
-return _heap.empty()?_heap.top():INVALID;
+return _heap->empty()?_heap->top():INVALID;
 }
 ///\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(); }
+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(); }
+int queueSize() { return _heap->size(); }
 ///Executes the algorithm.
 ///Executes the algorithm.
 ///
 ///- The shortest path tree.
 ///- The distance of each node from the root(s).
 ///
 void start()
 {
-while ( !_heap.empty() ) processNextNode();
+while ( !_heap->empty() ) processNextNode();
 }
 ///Executes the algorithm until \c dest is reached.
 ///Executes the algorithm until \c dest is reached.
 ///- 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();
+while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
-if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
+if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
 }
 ///Executes the algorithm until a condition is met.
 ///Executes the algorithm until a condition is met.
 ///\param nm must be a bool (or convertible) node map. The algorithm
 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
 template<class NodeBoolMap>
 void start(const NodeBoolMap &nm)
 {
-while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode();
+while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
-if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
+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
 ///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; }
+bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
 ///@}
 };
 typedef LM LengthMap;
 //The type of the length of the edges.
 typedef typename LM::Value Value;
 ///The heap type used by Dijkstra algorithm.
+/// The cross reference type used by heap.
+/// The cross reference type used by heap.
+/// Usually it is \c Graph::NodeMap<int>.
+typedef typename Graph::template NodeMap<int> HeapCrossRef;
+///Instantiates a HeapCrossRef.
+///This function instantiates a \ref HeapCrossRef.
+/// \param G is the graph, to which we would like to define the
+/// HeapCrossRef.
+/// \todo The graph alone may be insufficient for the initialization
+static HeapCrossRef *createHeapCrossRef(const GR &G)
+{
+return new HeapCrossRef(G);
+}
+///The heap type used by Dijkstra algorithm.
 ///The heap type used by Dijkstra algorithm.
 ///
 ///\sa BinHeap
 ///\sa Dijkstra
-typedef BinHeap<typename Graph::Node,
+typedef BinHeap<typename Graph::Node, typename LM::Value,
-		    typename LM::Value,
 		    typename GR::template NodeMap<int>,
 		    std::less<Value> > Heap;
+static Heap *createHeap(HeapCrossRef& R)
+{
+return new Heap(R);
+}
 ///\brief The type of the map that stores the last
 ///edges of the shortest paths.
 ///
 ///The type of the map that stores the last
 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;
 /// 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,
 /// \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
 /// 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
+/// it initiates a plain \ref Dijkstra class, and calls the \ref
-/// method of it.
+/// Dijkstra::run method of it.
 template<class TR>
 class DijkstraWizard : public TR
 {
 typedef TR Base;
 ///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() {}
 {
 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::_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>
-//     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<class T>
-//     DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
-//     {
-//       Base::_predNode=(void *)&t;
-//       return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
-//     }
 template<class T>
 struct DefDistMapBase : public Base {
 typedef T DistMap;
 static DistMap *createDistMap(const Graph &) { return 0; };
 DefDistMapBase(const TR &b) : TR(b) {}

changeset 1727	0c7d717b9538
parent 1710	f531c16dd923
child 1734	2fb5ceac10e7