Changeset 247:fefccf1bdc23 in lemon0.x
 Timestamp:
 03/26/04 15:03:02 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@347
 Location:
 src/work/alpar/dijkstra
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/dijkstra/dijkstra.cc
r222 r247 30 30 //double pre_time=currTime(); 31 31 tim.reset(); 32 Dijkstra <SmartGraph, 33 SmartGraph::EdgeMap<int>, 34 FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > 35 > dijkstra_test(G, cap); 32 // Dijkstra <SmartGraph, 33 // SmartGraph::EdgeMap<int>, 34 // FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > 35 // > dijkstra_test(G, cap); 36 37 Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, FibHeap > 38 dijkstra_test(G, cap); 36 39 37 40 dijkstra_test.run(s); … … 45 48 //pre_time=currTime(); 46 49 tim.reset(); 47 Dijkstra < SmartGraph, 48 SmartGraph::EdgeMap<int>, 49 BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > > 50 dijkstra_test2(G, cap); 50 // Dijkstra < SmartGraph, 51 // SmartGraph::EdgeMap<int>, 52 // BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > > 53 // dijkstra_test2(G, cap); 54 55 Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, BinHeap > 56 dijkstra_test2(G, cap); 51 57 52 58 dijkstra_test2.run(s); 
src/work/alpar/dijkstra/dijkstra.h
r242 r247 69 69 template <typename Graph, 70 70 typename LengthMap=typename Graph::EdgeMap<int>, 71 typename Heap=BinHeap <typename Graph::Node, 72 typename LengthMap::ValueType, 73 typename Graph::NodeMap<int> > > 71 template <class,class,class> class Heap = BinHeap > 72 // typename Heap=BinHeap <typename Graph::Node, 73 // typename LengthMap::ValueType, 74 // typename Graph::NodeMap<int> > > 74 75 #endif 75 76 class Dijkstra{ … … 105 106 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } 106 107 107 108 108 void run(Node s); 109 109 … … 174 174 /// The shortest path tree. 175 175 /// The distance of each node from the source. 176 template <typename Graph, typename LengthMap, typename Heap > 176 template <typename Graph, typename LengthMap, 177 template<class,class,class> class Heap > 177 178 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { 178 179 … … 192 193 typename Graph::NodeMap<int> heap_map(G,1); 193 194 194 Heap heap(heap_map); 195 //Heap heap(heap_map); 196 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map); 195 197 196 198 heap.push(s,0); … … 208 210 209 211 switch(heap.state(w)) { 210 case Heap::PRE_HEAP:212 case heap.PRE_HEAP: 211 213 // reach.set(w,true); 212 214 heap.push(w,oldvalue+length[e]); … … 214 216 pred_node.set(w,v); 215 217 break; 216 case Heap::IN_HEAP:218 case heap.IN_HEAP: 217 219 if ( oldvalue+length[e] < heap[w] ) { 218 220 heap.decrease(w, oldvalue+length[e]); … … 221 223 } 222 224 break; 223 case Heap::POST_HEAP:225 case heap.POST_HEAP: 224 226 break; 225 227 }
Note: See TracChangeset
for help on using the changeset viewer.