COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/dijkstra.hh @ 33:f505c414feb9

Last change on this file since 33:f505c414feb9 was 33:f505c414feb9, checked in by jacint, 17 years ago

Primitive Dijkstra with stl priority queue. flow_test.cc is for testing flows and Dijkstra.

File size: 4.0 KB
Line 
1/*
2 *dijkstra
3 *by jacint
4 *Performs Dijkstra's algorithm from node s.
5 *
6 *Constructor:
7 *
8 *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance)
9 *
10 *
11 *
12 *Member functions:
13 *
14 *void run()
15 *
16 *  The following function should be used after run() was already run.
17 *
18 *
19 *T dist(node_iterator v) : returns the distance from s to v.
20 *   It is 0 if v is not reachable from s.
21 *
22 *
23 *edge_iterator pred(node_iterator v)
24 *   Returns the last edge of a shortest s-v path.
25 *   Returns an invalid iterator if v=s or v is not
26 *   reachable from s.
27 *
28 *
29 *bool reach(node_iterator v) : true if v is reachable from s
30 *
31 *
32 *
33 *
34 *
35 *Problems:
36 *
37 *Heap implementation is needed, because the priority queue of stl
38 *does not have a mathod for key-decrease, so we had to use here a
39 *g\'any solution.
40 *
41 *The implementation of infinity would be desirable, see after line 100.
42 */
43
44#ifndef DIJKSTRA_HH
45#define DIJKSTRA_HH
46
47#include <queue>
48#include <algorithm>
49
50#include <marci_graph_traits.hh>
51#include <marci_property_vector.hh>
52
53
54namespace std {
55  namespace marci {
56
57
58
59
60
61    template <typename graph_type, typename T>
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;
68     
69     
70      graph_type& G;
71      node_iterator s;
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;
76         
77  public :
78
79    /*
80      The distance of all the nodes is 0.
81    */
82    dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<graph_type, T>& _length) :
83      G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { }
84   
85
86     
87      /*By Misi.*/
88      struct node_dist_comp
89      {
90        node_property_vector<graph_type, T> &d;
91        node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {}
92       
93        bool operator()(const node_iterator& u, const node_iterator& v) const
94        { return d.get(u) < d.get(v); }
95      };
96
97
98     
99      void run() {
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) ));
104     
105        heap.push(s);
106        reached.put(s, true);
107
108        while (!heap.empty()) {
109
110          node_iterator v=heap.top();   
111          heap.pop();
112
113
114          if (!scanned.get(v)) {
115       
116            for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) {
117              node_iterator w=G.head(e);
118
119              if (!scanned.get(w)) {
120                if (!reached.get(w)) {
121                  reached.put(w,true);
122                  distance.put(w, distance.get(v)-length.get(e));
123                  predecessor.put(w,e);
124                } else if (distance.get(v)-length.get(e)>distance.get(w)) {
125                  distance.put(w, distance.get(v)-length.get(e));
126                  predecessor.put(w,e);
127                }
128               
129                heap.push(w);
130             
131              }
132
133            }
134            scanned.put(v,true);
135           
136          } // if (!scanned.get(v))
137         
138         
139         
140        } // while (!heap.empty())
141
142       
143      } //void run()
144     
145     
146     
147
148
149      /*
150       *Returns the distance of the node v.
151       *It is 0 for the root and for the nodes not
152       *reachable form the root.
153       */     
154      T dist(node_iterator v) {
155        return -distance.get(v);
156      }
157
158
159
160      /*
161       *  Returns the last edge of a shortest s-v path.
162       *  Returns an invalid iterator if v=root or v is not
163       *  reachable from the root.
164       */     
165      edge_iterator pred(node_iterator v) {
166        if (v!=s) { return predecessor.get(v);}
167        else {return edge_iterator();}
168      }
169     
170
171     
172      bool reach(node_iterator v) {
173        return reached.get(v);
174      }
175
176
177
178
179
180
181
182
183
184    };// class dijkstra
185
186
187
188  } // namespace marci
189}
190#endif //DIJKSTRA_HH
191
192
Note: See TracBrowser for help on using the repository browser.