Index: lemon/dijkstra.h
===================================================================
--- lemon/dijkstra.h	(revision 1710)
+++ lemon/dijkstra.h	(revision 1721)
@@ -51,4 +51,20 @@
     //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.
 
@@ -60,4 +76,9 @@
 		    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
@@ -196,4 +217,6 @@
     ///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;
@@ -215,4 +238,12 @@
     ///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.
@@ -233,4 +264,12 @@
 	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);
       }
     }
@@ -316,11 +355,32 @@
       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:
 
@@ -338,5 +398,6 @@
       _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)
     { }
     
@@ -347,4 +408,6 @@
       if(local_dist) delete _dist;
       if(local_processed) delete _processed;
+      if(local_heap_cross_ref) delete _heap_cross_ref;
+      if(local_heap) delete _heap;
     }
 
@@ -417,14 +480,12 @@
     ///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);
       }
     }
@@ -441,7 +502,8 @@
     void addSource(Node s,Value dst=0)
     {
-      if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
-      else if(_heap[s]<dst) {
-	_heap.push(s,dst);
+      if(_heap->state(s) != Heap::IN_HEAP) {
+	_heap->push(s,dst);
+      } else if((*_heap)[s]<dst) {
+	_heap->push(s,dst);
 	_pred->set(s,INVALID);
       }
@@ -457,19 +519,19 @@
     Node processNextNode()
     {
-      Node v=_heap.top(); 
-      Value oldvalue=_heap[v];
-      _heap.pop();
+      Node v=_heap->top(); 
+      Value oldvalue=_heap->prio();
+      _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] ) {
-	    _heap.decrease(w, oldvalue+(*length)[e]); 
+	  if ( oldvalue+(*length)[e] < (*_heap)[w] ) {
+	    _heap->decrease(w, oldvalue+(*length)[e]); 
 	    _pred->set(w,e);
 	  }
@@ -490,5 +552,5 @@
     Node nextNode()
     { 
-      return _heap.empty()?_heap.top():INVALID;
+      return _heap->empty()?_heap->top():INVALID;
     }
  
@@ -498,10 +560,10 @@
     ///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.
@@ -521,5 +583,5 @@
     void start()
     {
-      while ( !_heap.empty() ) processNextNode();
+      while ( !_heap->empty() ) processNextNode();
     }
     
@@ -540,6 +602,6 @@
     void start(Node dest)
     {
-      while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
-      if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
+      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
+      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
     }
     
@@ -556,6 +618,6 @@
     void start(const NodeBoolMap &nm)
     {
-      while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode();
-      if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
+      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
+      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
     }
     
@@ -684,5 +746,5 @@
     ///\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; }
     
     ///@}
@@ -712,12 +774,34 @@
     ///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,
-		    typename LM::Value,
+    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
@@ -808,6 +892,4 @@
     ///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;
@@ -821,5 +903,4 @@
     /// all of the attributes to default values (0, INVALID).
     DijkstraWizardBase() : _g(0), _length(0), _pred(0),
-// 			   _predNode(0),
 			   _dist(0), _source(INVALID) {}
 
@@ -834,5 +915,4 @@
     DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
       _g((void *)&g), _length((void *)&l), _pred(0),
-//       _predNode(0),
       _dist(0), _source(s) {}
 
@@ -856,6 +936,6 @@
   ///
   /// 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.
+  /// it initiates a plain \ref Dijkstra class, and calls the \ref 
+  /// Dijkstra::run method of it.
   template<class TR>
   class DijkstraWizard : public TR
@@ -881,10 +961,6 @@
     ///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;
@@ -915,5 +991,4 @@
 	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);
@@ -950,25 +1025,4 @@
     }
     
-
-//     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 {
