Changeset 247:fefccf1bdc23 in lemon-0.x for src/work
- Timestamp:
- 03/26/04 15:03:02 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/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.