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

Timestamp:

10/26/05 12:50:47 (19 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/dijkstra.h (modified) (5 diffs)

lemon/dijkstra.h

@@ -62 +62 @@
     /// \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) 
     {
@@ -75 +74 @@
     ///\sa Dijkstra
     typedef BinHeap<typename Graph::Node, typename LM::Value,
-                    typename GR::template NodeMap<int>,
-                    std::less<Value> > Heap;
+                    HeapCrossRef, std::less<Value> > Heap;
 
     static Heap *createHeap(HeapCrossRef& R) 
@@ -361 +359 @@
       typedef CR HeapCrossRef;
       typedef H Heap;
-      static HeapCrossRef *createHeapCrossRef(const Graph &G) {
-        return new HeapCrossRef(G);
-      }
-      static Heap *createHeap(HeapCrossRef &R) 
+      static HeapCrossRef *createHeapCrossRef(const Graph &) {
+        throw UninitializedParameter();
+      }
+      static Heap *createHeap(HeapCrossRef &) 
       {
-        return new Heap(R);
+        throw UninitializedParameter();
       }
     };
@@ -379 +377 @@
       : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > { 
       typedef Dijkstra< 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 Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> > { 
+      typedef Dijkstra< Graph,  LengthMap, DefStandardHeapTraits<H, CR> > 
+      Create;
     };
     
@@ -454 +478 @@
       }
       _dist = &m;
+      return *this;
+    }
+
+    ///Sets the heap and the cross reference used by algorithm.
+
+    ///Sets the heap and the cross reference used by algorithm.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///automatically allocated map, of course.
+    ///\return <tt> (*this) </tt>
+    Dijkstra &heap(Heap& heap, HeapCrossRef &crossRef)
+    {
+      if(local_heap_cross_ref) {
+        delete _heap_cross_ref;
+        local_heap_cross_ref=false;
+      }
+      _heap_cross_ref = &crossRef;
+      if(local_heap) {
+        delete _heap;
+        local_heap=false;
+      }
+      _heap = &heap;
       return *this;
     }