Changeset 211:9222a9b8b323 in lemon0.x for src/work/jacint/dijkstra.h
 Timestamp:
 03/19/04 23:16:05 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@306
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/dijkstra.h
r171 r211 1 1 // * C++ * 2 3 //ha predecessor az elejen nem invalid, akkor hagyd csak ugy4 //scanned mutatja hogy jo ertek vane benne vagy szemet5 6 2 /* 7 *template <Graph, T, Heap=FibHeap >3 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> > 8 4 * 9 5 *Constructor: 10 6 * 11 *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T>length)7 *Dijkstra(Graph G, LengthMap length) 12 8 * 13 9 * 14 *Me mber functions:10 *Methods: 15 11 * 16 *void run( )12 *void run(Node s) 17 13 * 18 * The following function should be used after run() was already run. 14 *T dist(Node v) : After run(s) was run, it returns the distance from s to v. 15 * Returns T() if v is not reachable from s. 19 16 * 20 *T dist(NodeIt v) : returns the distance from s to v. 21 * It is 0 if v is not reachable from s. 17 *Edge pred(Node v) : After run(s) was run, it returns the last 18 * edge of a shortest sv path. It is INVALID for s and for 19 * the nodes not reachable from s. 22 20 * 23 *EdgeIt pred(NodeIt v) : returns the last edge 24 * of a shortest sv path. Returns an invalid iterator 25 * if v=s or v is not reachable from s. 26 * 27 *bool reach(NodeIt v) : true iff v is reachable from s 21 *bool reached(Node v) : After run(s) was run, it is true iff v is 22 * reachable from s 28 23 * 29 24 */ 30 25 31 #ifndef DIJKSTRA_H32 #define DIJKSTRA_H26 #ifndef HUGO_DIJKSTRA_H 27 #define HUGO_DIJKSTRA_H 33 28 34 29 #include <fib_heap.h> 30 #include <invalid.h> 35 31 36 32 namespace hugo { 37 33 38 34 template <typename Graph, typename T, 39 typename Heap=FibHeap<typename Graph::NodeIt, T, 40 typename Graph::NodeMap<int> > > 41 class Dijkstra{ 42 typedef typename Graph::NodeIt NodeIt; 43 typedef typename Graph::EdgeIt EdgeIt; 44 typedef typename Graph::OutEdgeIt OutEdgeIt; 45 46 Graph& G; 47 NodeIt s; 48 typename Graph::NodeMap<EdgeIt> predecessor; 49 typename Graph::NodeMap<T> distance; 50 typename Graph::EdgeMap<T>& length; 51 typename Graph::NodeMap<bool> reached; 52 35 typename Heap=FibHeap<typename Graph::Node, T, 36 typename Graph::NodeMap<int> >, 37 typename LengthMap=typename Graph::EdgeMap<T> > 38 class Dijkstra{ 39 typedef typename Graph::Node Node; 40 typedef typename Graph::NodeIt NodeIt; 41 typedef typename Graph::Edge Edge; 42 typedef typename Graph::OutEdgeIt OutEdgeIt; 43 44 const Graph& G; 45 const LengthMap& length; 46 typename Graph::NodeMap<Edge> predecessor; 47 typename Graph::NodeMap<T> distance; 48 typename Graph::NodeMap<bool> reach; 49 53 50 public : 54 51 55 52 /* 56 53 The distance of the nodes is 0. 57 54 */ 58 Dijkstra(Graph& _G, NodeIt const _s, 59 typename Graph::EdgeMap<T>& _length) : 60 G(_G), s(_s), predecessor(G), distance(G), 61 length(_length), reached(G, false) { } 55 Dijkstra(Graph& _G, LengthMap& _length) : G(_G), 56 length(_length), predecessor(_G), distance(_G), reach(_G) { } 62 57 58 59 void run(Node s) { 63 60 64 void run() { 61 NodeIt u; 62 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { 63 predecessor.set(u,INVALID); 64 distance.set(u,0); 65 reach.set(u,false); 66 } 67 68 typename Graph::NodeMap<bool> scanned(G,false); 69 typename Graph::NodeMap<int> heap_map(G,1); 70 71 Heap heap(heap_map); 72 73 heap.push(s,0); 74 reach.set(s, true); 75 76 while ( !heap.empty() ) { 65 77 66 typename Graph::NodeMap<bool> scanned(G, false); 67 typename Graph::NodeMap<int> heap_map(G,1); 78 Node v=heap.top(); 79 T oldvalue=heap.get(v); 80 heap.pop(); 81 distance.set(v, oldvalue); 82 scanned.set(v,true); 68 83 69 Heap heap(heap_map); 70 71 heap.push(s,0); 72 reached.set(s, true); 73 74 while ( !heap.empty() ) { 75 76 NodeIt v=heap.top(); 77 T oldvalue=heap.get(v); 78 heap.pop(); 79 distance.set(v, oldvalue); 80 scanned.set(v,true); 81 82 OutEdgeIt e; 83 for( G.getFirst(e,v); G.valid(e); G.next(e)) { 84 NodeIt w=G.bNode(e); 84 OutEdgeIt e; 85 for( G.first(e,v); G.valid(e); G.next(e)) { 86 Node w=G.head(e); 85 87 86 if ( !scanned.get(w) ) { 87 if ( !reached.get(w) ) { 88 reached.set(w,true); 89 heap.push(w,oldvalue+length.get(e)); 90 predecessor.set(w,e); 91 } else if ( oldvalue+length.get(e) < heap.get(w) ) { 92 predecessor.set(w,e); 93 heap.decrease(w, oldvalue+length.get(e)); 94 } 88 if ( !scanned[w] ) { 89 if ( !reach[w] ) { 90 reach.set(w,true); 91 heap.push(w,oldvalue+length[e]); 92 predecessor.set(w,e); 93 } else if ( oldvalue+length[e] < heap.get(w) ) { 94 predecessor.set(w,e); 95 heap.decrease(w, oldvalue+length[e]); 95 96 } 96 97 } 97 98 } 98 } 99 99 } 100 } 101 100 102 101 T dist(NodeItv) {102 return distance.get(v);103 103 T dist(Node v) { 104 return distance[v]; 105 } 104 106 105 107 106 EdgeIt pred(NodeIt v) { 107 if ( v!=s ) return predecessor.get(v); 108 else return EdgeIt(); 109 } 108 Edge pred(Node v) { 109 return predecessor[v]; 110 } 110 111 111 112 112 bool reach(NodeItv) {113 return reached.get(v);114 115 116 113 bool reached(Node v) { 114 return reach[v]; 115 } 116 117 }; 117 118 118 119 }
Note: See TracChangeset
for help on using the changeset viewer.