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