diff -r 4cade8579363 -r 7a98fe2ed989 lemon/johnson.h
--- a/lemon/johnson.h	Mon Oct 24 17:03:02 2005 +0000
+++ b/lemon/johnson.h	Wed Oct 26 10:50:47 2005 +0000
@@ -106,6 +106,38 @@
     /// and the used operation.
     /// \see JohnsonDefaultOperationTraits
     typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
+
+    /// 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 graph is the graph, to which we would like to define the 
+    /// HeapCrossRef.
+    static HeapCrossRef *createHeapCrossRef(const Graph& graph) {
+      return new HeapCrossRef(graph);
+    }
+    
+    ///The heap type used by Dijkstra algorithm.
+
+    ///The heap type used by Dijkstra algorithm.
+    ///
+    ///\sa BinHeap
+    ///\sa Dijkstra
+    typedef BinHeap<typename Graph::Node, typename LengthMap::Value,
+		    HeapCrossRef, std::less<Value> > Heap;
+
+    ///Instantiates a Heap.
+
+    ///This function instantiates a \ref Heap. 
+    /// \param crossRef The cross reference for the heap.
+    static Heap *createHeap(HeapCrossRef& crossRef) {
+      return new Heap(crossRef);
+    }
  
     /// \brief The type of the matrix map that stores the last edges of the 
     /// shortest paths.
@@ -121,7 +153,7 @@
     /// 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 _Graph& graph) {
+    static PredMap *createPredMap(const Graph& graph) {
       return new PredMap(graph);
     }
 
@@ -158,7 +190,9 @@
   /// should be used from each node.
   ///
   /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
-  /// with fibonacci heap O(n^2 * log(n) + n * e).
+  /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap
+  /// implementation is slower than either binary heap implementation or the 
+  /// Floyd-Warshall algorithm. 
   ///
   /// The type of the length is determined by the
   /// \ref concept::ReadMap::Value "Value" of the length map.
@@ -225,6 +259,10 @@
     typedef typename _Traits::DistMap DistMap;
     /// \brief The operation traits.
     typedef typename _Traits::OperationTraits OperationTraits;
+    ///The cross reference type used for the current heap.
+    typedef typename _Traits::HeapCrossRef HeapCrossRef;
+    ///The heap type used by the dijkstra algorithm.
+    typedef typename _Traits::Heap Heap;
   private:
     /// Pointer to the underlying graph.
     const Graph *graph;
@@ -238,6 +276,14 @@
     DistMap *_dist;
     ///Indicates if \ref _dist is locally allocated (\c true) or not.
     bool local_dist;
+    ///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.
     void create_maps() {
@@ -249,9 +295,19 @@
 	local_dist = true;
 	_dist = Traits::createDistMap(*graph);
       }
+      if (!_heap_cross_ref) {
+	local_heap_cross_ref = true;
+	_heap_cross_ref = Traits::createHeapCrossRef(*graph);
+      }
+      if (!_heap) {
+	local_heap = true;
+	_heap = Traits::createHeap(*_heap_cross_ref);
+      }
     }
-    
+
   public :
+
+    typedef Johnson Create;
  
     /// \name Named template parameters
 
@@ -308,6 +364,56 @@
       : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {
       typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
     };
+
+    template <class H, class CR>
+    struct DefHeapTraits : public Traits {
+      typedef CR HeapCrossRef;
+      typedef H Heap;
+      static HeapCrossRef *createHeapCrossRef(const Graph &) {
+	throw UninitializedParameter();
+      }
+      static Heap *createHeap(HeapCrossRef &) 
+      {
+	throw UninitializedParameter();
+      }
+    };
+    ///\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 Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > { 
+      typedef Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
+    };
+
+    template <class H, class CR>
+    struct DefStandardHeapTraits : 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 with automatic allocation
+
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type. It can allocate the heap and the cross reference 
+    ///object if the cross reference's constructor waits for the graph as 
+    ///parameter and the heap's constructor waits for the cross reference.
+    template <class H, class CR = typename Graph::template NodeMap<int> >
+    struct DefStandardHeap
+      : public Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > { 
+      typedef Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > 
+      Create;
+    };
     
     ///@}
 
@@ -316,6 +422,8 @@
     Johnson() {}
 
   public:      
+
+    typedef Johnson Create;
     
     /// \brief Constructor.
     ///
@@ -324,12 +432,16 @@
     Johnson(const Graph& _graph, const LengthMap& _length) :
       graph(&_graph), length(&_length),
       _pred(0), local_pred(false),
-      _dist(0), local_dist(false) {}
+      _dist(0), local_dist(false),
+      _heap_cross_ref(0), local_heap_cross_ref(false),
+      _heap(0), local_heap(false) {}
     
     ///Destructor.
     ~Johnson() {
-      if(local_pred) delete _pred;
-      if(local_dist) delete _dist;
+      if (local_pred) delete _pred;
+      if (local_dist) delete _dist;
+      if (local_heap_cross_ref) delete _heap_cross_ref;
+      if (local_heap) delete _heap;
     }
 
     /// \brief Sets the length map.
@@ -373,6 +485,43 @@
       return *this;
     }
 
+  protected:
+    
+    typedef typename BelmannFord<Graph, LengthMap>::
+    template DefOperationTraits<OperationTraits>::
+    template DefPredMap<NullMap<Node, Edge> >::
+    Create BelmannFordType;
+
+    void shiftedRun(const BelmannFordType& belmannford) {
+      
+      typedef PotentialDifferenceMap<Graph, 
+      typename BelmannFordType::DistMap> PotDiffMap;
+      PotDiffMap potdiff(*graph, belmannford.distMap());
+      typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
+      ShiftLengthMap shiftlen(*length, potdiff);
+
+      typename Dijkstra<Graph, ShiftLengthMap>::
+      template DefHeap<Heap, HeapCrossRef>::Create dijkstra(*graph, shiftlen);
+
+      dijkstra.heap(*_heap, *_heap_cross_ref);
+      
+      for (NodeIt it(*graph); it != INVALID; ++it) {
+	dijkstra.run(it);
+	for (NodeIt jt(*graph); jt != INVALID; ++jt) {
+	  if (dijkstra.reached(jt)) {
+	    _dist->set(it, jt, dijkstra.dist(jt) + 
+		       belmannford.dist(jt) - belmannford.dist(it));
+	    _pred->set(it, jt, dijkstra.pred(jt));
+	  } else {
+	    _dist->set(it, jt, OperationTraits::infinity());
+	    _pred->set(it, jt, INVALID);
+	  }
+	}
+      }
+    }
+
+  public:    
+
     ///\name Execution control
     /// The simplest way to execute the algorithm is to use
     /// one of the member functions called \c run(...).
@@ -389,7 +538,7 @@
     void init() {
       create_maps();
     }
-    
+
     /// \brief Executes the algorithm.
     ///
     /// This method runs the %Johnson algorithm in order to compute 
@@ -398,10 +547,6 @@
     /// - The shortest path tree for each node.
     /// - The distance between each node pairs.
     void start() {
-      typedef typename BelmannFord<Graph, LengthMap>::
-      template DefOperationTraits<OperationTraits>::
-      template DefPredMap<NullMap<Node, Edge> >::
-      Create BelmannFordType;
 
       BelmannFordType belmannford(*graph, *length);
 
@@ -412,26 +557,32 @@
       belmannford.init(OperationTraits::zero());
       belmannford.start();
 
-      for (NodeIt it(*graph); it != INVALID; ++it) {
-	typedef PotentialDifferenceMap<Graph, 
-	  typename BelmannFordType::DistMap> PotDiffMap;
-	PotDiffMap potdiff(*graph, belmannford.distMap());
-	typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
-	ShiftLengthMap shiftlen(*length, potdiff);
-	Dijkstra<Graph, ShiftLengthMap> dijkstra(*graph, shiftlen); 
-	dijkstra.run(it);
-	for (NodeIt jt(*graph); jt != INVALID; ++jt) {
-	  if (dijkstra.reached(jt)) {
-	    _dist->set(it, jt, dijkstra.dist(jt) + 
-		       belmannford.dist(jt) - belmannford.dist(it));
-	    _pred->set(it, jt, dijkstra.pred(jt));
-	  } else {
-	    _dist->set(it, jt, OperationTraits::infinity());
-	    _pred->set(it, jt, INVALID);
-	  }
-	}
-      }
+      shiftedRun(belmannford);
     }
+
+    /// \brief Executes the algorithm and checks the negatvie circles.
+    ///
+    /// This method runs the %Johnson algorithm in order to compute 
+    /// the shortest path to each node pairs. If the graph contains
+    /// negative circle it gives back false. The algorithm 
+    /// computes 
+    /// - The shortest path tree for each node.
+    /// - The distance between each node pairs.
+    bool checkedStart() {
+
+      BelmannFordType belmannford(*graph, *length);
+
+      NullMap<Node, Edge> predMap;
+
+      belmannford.predMap(predMap);
+      
+      belmannford.init(OperationTraits::zero());
+      if (!belmannford.checkedStart()) return false;
+
+      shiftedRun(belmannford);
+      return true;
+    }
+
     
     /// \brief Runs %Johnson algorithm.
     ///