Changeset 247:fefccf1bdc23 in lemon-0.x for src

Timestamp:

03/26/04 15:03:02 (21 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

Heap is now a template-template parameter

Location:

src/work/alpar/dijkstra

Files:

• dijkstra.cc (modified) (2 diffs)
• dijkstra.h (modified) (7 diffs)

src/work/alpar/dijkstra/dijkstra.cc

@@ -30 +30 @@
   //double pre_time=currTime();
   tim.reset();
-  Dijkstra <SmartGraph,
-    SmartGraph::EdgeMap<int>,
-    FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> >
-    > dijkstra_test(G, cap); 
+//   Dijkstra <SmartGraph,
+//     SmartGraph::EdgeMap<int>,
+//     FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> >
+//     > dijkstra_test(G, cap); 
+  
+  Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, FibHeap >
+    dijkstra_test(G, cap); 
   
   dijkstra_test.run(s);
@@ -45 +48 @@
   //pre_time=currTime();
   tim.reset();
-  Dijkstra < SmartGraph,
-    SmartGraph::EdgeMap<int>,
-    BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > > 
-    dijkstra_test2(G, cap);
+//   Dijkstra < SmartGraph,
+//     SmartGraph::EdgeMap<int>,
+//     BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > > 
+//     dijkstra_test2(G, cap);
+  
+  Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, BinHeap >
+    dijkstra_test2(G, cap); 
   
   dijkstra_test2.run(s);

src/work/alpar/dijkstra/dijkstra.h

@@ -69 +69 @@
   template <typename Graph,
             typename LengthMap=typename Graph::EdgeMap<int>,
-            typename Heap=BinHeap <typename Graph::Node,
-                                   typename LengthMap::ValueType, 
-                                   typename Graph::NodeMap<int> > >
+            template <class,class,class> class Heap = BinHeap >
+//          typename Heap=BinHeap <typename Graph::Node,
+//                                 typename LengthMap::ValueType, 
+//                                 typename Graph::NodeMap<int> > >
 #endif
   class Dijkstra{
@@ -105 +106 @@
       G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
     
-
     void run(Node s);
     
@@ -174 +174 @@
   ///- The shortest path tree.
   ///- The distance of each node from the source.
-  template <typename Graph, typename LengthMap, typename Heap >
+  template <typename Graph, typename LengthMap,
+            template<class,class,class> class Heap >
   void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
     
@@ -192 +193 @@
     typename Graph::NodeMap<int> heap_map(G,-1);
     
-    Heap heap(heap_map);
+    //Heap heap(heap_map);
+    Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
     
     heap.push(s,0); 
@@ -208 +210 @@
           
           switch(heap.state(w)) {
-          case Heap::PRE_HEAP:
+          case heap.PRE_HEAP:
             //      reach.set(w,true);
             heap.push(w,oldvalue+length[e]); 
@@ -214 +216 @@
             pred_node.set(w,v);
             break;
-          case Heap::IN_HEAP:
+          case heap.IN_HEAP:
             if ( oldvalue+length[e] < heap[w] ) {
               heap.decrease(w, oldvalue+length[e]); 
@@ -221 +223 @@
             }
             break;
-          case Heap::POST_HEAP:
+          case heap.POST_HEAP:
             break;
           }