Changeset 78:ecc1171307be in lemon-0.x for src/work/jacint/dijkstra.hh
- Timestamp:
- 02/16/04 17:15:58 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@101
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/dijkstra.hh
r50 r78 2 2 *dijkstra 3 3 *by jacint 4 *Performs Dijkstra's algorithm from node s.4 *Performs Dijkstra's algorithm from Node s. 5 5 * 6 6 *Constructor: 7 7 * 8 *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance)8 *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance) 9 9 * 10 10 * … … 17 17 * 18 18 * 19 *T dist( node_iteratorv) : returns the distance from s to v.19 *T dist(NodeIt v) : returns the distance from s to v. 20 20 * It is 0 if v is not reachable from s. 21 21 * 22 22 * 23 * edge_iterator pred(node_iteratorv)24 * Returns the last edge of a shortest s-v path.23 *EdgeIt pred(NodeIt v) 24 * Returns the last Edge of a shortest s-v path. 25 25 * Returns an invalid iterator if v=s or v is not 26 26 * reachable from s. 27 27 * 28 28 * 29 *bool reach( node_iteratorv) : true if v is reachable from s29 *bool reach(NodeIt v) : true if v is reachable from s 30 30 * 31 31 * … … 49 49 50 50 #include <marci_graph_traits.hh> 51 #include <marci _property_vector.hh>51 #include <marciMap.hh> 52 52 53 53 … … 61 61 template <typename graph_type, typename T> 62 62 class dijkstra{ 63 typedef typename graph_traits<graph_type>:: node_iterator node_iterator;64 typedef typename graph_traits<graph_type>:: edge_iterator edge_iterator;65 typedef typename graph_traits<graph_type>:: each_node_iterator each_node_iterator;66 typedef typename graph_traits<graph_type>:: in_edge_iterator in_edge_iterator;67 typedef typename graph_traits<graph_type>:: out_edge_iterator out_edge_iterator;63 typedef typename graph_traits<graph_type>::NodeIt NodeIt; 64 typedef typename graph_traits<graph_type>::EdgeIt EdgeIt; 65 typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt; 66 typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt; 67 typedef typename graph_traits<graph_type>::OutEdgeIt OutEdgeIt; 68 68 69 69 70 70 graph_type& G; 71 node_iterators;72 node_property_vector<graph_type, edge_iterator> predecessor;73 node_property_vector<graph_type, T> distance;74 edge_property_vector<graph_type, T> length;75 node_property_vector<graph_type, bool> reached;71 NodeIt s; 72 NodeMap<graph_type, EdgeIt> predecessor; 73 NodeMap<graph_type, T> distance; 74 EdgeMap<graph_type, T> length; 75 NodeMap<graph_type, bool> reached; 76 76 77 77 public : 78 78 79 79 /* 80 The distance of all the nodes is 0.80 The distance of all the Nodes is 0. 81 81 */ 82 dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<graph_type, T>& _length) :82 dijkstra(graph_type& _G, NodeIt _s, EdgeMap<graph_type, T>& _length) : 83 83 G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { } 84 84 … … 86 86 87 87 /*By Misi.*/ 88 struct node_dist_comp88 struct Node_dist_comp 89 89 { 90 node_property_vector<graph_type, T> &d;91 node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {}90 NodeMap<graph_type, T> &d; 91 Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} 92 92 93 bool operator()(const node_iterator& u, const node_iterator& v) const93 bool operator()(const NodeIt& u, const NodeIt& v) const 94 94 { return d.get(u) < d.get(v); } 95 95 }; … … 99 99 void run() { 100 100 101 node_property_vector<graph_type, bool> scanned(G, false);102 std::priority_queue< node_iterator, vector<node_iterator>, node_dist_comp>103 heap(( node_dist_comp(distance) ));101 NodeMap<graph_type, bool> scanned(G, false); 102 std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp> 103 heap(( Node_dist_comp(distance) )); 104 104 105 105 heap.push(s); … … 108 108 while (!heap.empty()) { 109 109 110 node_iteratorv=heap.top();110 NodeIt v=heap.top(); 111 111 heap.pop(); 112 112 … … 114 114 if (!scanned.get(v)) { 115 115 116 for( out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) {117 node_iteratorw=G.head(e);116 for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) { 117 NodeIt w=G.head(e); 118 118 119 119 if (!scanned.get(w)) { … … 148 148 149 149 /* 150 *Returns the distance of the node v.151 *It is 0 for the root and for the nodes not150 *Returns the distance of the Node v. 151 *It is 0 for the root and for the Nodes not 152 152 *reachable form the root. 153 153 */ 154 T dist( node_iteratorv) {154 T dist(NodeIt v) { 155 155 return -distance.get(v); 156 156 } … … 159 159 160 160 /* 161 * Returns the last edge of a shortest s-v path.161 * Returns the last Edge of a shortest s-v path. 162 162 * Returns an invalid iterator if v=root or v is not 163 163 * reachable from the root. 164 164 */ 165 edge_iterator pred(node_iteratorv) {165 EdgeIt pred(NodeIt v) { 166 166 if (v!=s) { return predecessor.get(v);} 167 else {return edge_iterator();}167 else {return EdgeIt();} 168 168 } 169 169 170 170 171 171 172 bool reach( node_iteratorv) {172 bool reach(NodeIt v) { 173 173 return reached.get(v); 174 174 }
Note: See TracChangeset
for help on using the changeset viewer.