Changeset 1741:7a98fe2ed989 in lemon-0.x for lemon/johnson.h

Timestamp:

10/26/05 12:50:47 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2269

Message:

Some modifications on shortest path algoritms:

• heap traits
• checked execution

File:

• lemon/johnson.h (modified) (11 diffs)

lemon/johnson.h

@@ -107 +107 @@
     /// \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 
@@ -122 +154 @@
     /// \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);
     }
@@ -159 +191 @@
   ///
   /// 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
@@ -226 +260 @@
     /// \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.
@@ -239 +277 @@
     ///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.
@@ -250 +296 @@
         _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
@@ -309 +365 @@
       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;
+    };
     
     ///@}
@@ -317 +423 @@
 
   public:      
+
+    typedef Johnson Create;
     
     /// \brief Constructor.
@@ -325 +433 @@
       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;
     }
 
@@ -374 +486 @@
     }
 
-    ///\name Execution control
-    /// The simplest way to execute the algorithm is to use
-    /// one of the member functions called \c run(...).
-    /// \n
-    /// If you need more control on the execution,
-    /// Finally \ref start() will perform the actual path
-    /// computation.
-
-    ///@{
-
-    /// \brief Initializes the internal data structures.
-    /// 
-    /// Initializes the internal data structures.
-    void init() {
-      create_maps();
-    }
-    
-    /// \brief Executes the algorithm.
-    ///
-    /// This method runs the %Johnson algorithm in order to compute 
-    /// the shortest path to each node pairs. The algorithm 
-    /// computes 
-    /// - 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);
-
-      NullMap<Node, Edge> predMap;
-
-      belmannford.predMap(predMap);
+  protected:
+    
+    typedef typename BelmannFord<Graph, LengthMap>::
+    template DefOperationTraits<OperationTraits>::
+    template DefPredMap<NullMap<Node, Edge> >::
+    Create BelmannFordType;
+
+    void shiftedRun(const BelmannFordType& belmannford) {
       
-      belmannford.init(OperationTraits::zero());
-      belmannford.start();
-
+      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) {
-        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) {
@@ -433 +520 @@
       }
     }
+
+  public:    
+
+    ///\name Execution control
+    /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \c run(...).
+    /// \n
+    /// If you need more control on the execution,
+    /// Finally \ref start() will perform the actual path
+    /// computation.
+
+    ///@{
+
+    /// \brief Initializes the internal data structures.
+    /// 
+    /// Initializes the internal data structures.
+    void init() {
+      create_maps();
+    }
+
+    /// \brief Executes the algorithm.
+    ///
+    /// This method runs the %Johnson algorithm in order to compute 
+    /// the shortest path to each node pairs. The algorithm 
+    /// computes 
+    /// - The shortest path tree for each node.
+    /// - The distance between each node pairs.
+    void start() {
+
+      BelmannFordType belmannford(*graph, *length);
+
+      NullMap<Node, Edge> predMap;
+
+      belmannford.predMap(predMap);
+      
+      belmannford.init(OperationTraits::zero());
+      belmannford.start();
+
+      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.