# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
Dijkstra.h
Go to the documentation of this file.
1
32#pragma once
33
35#include <ogdf/basic/Graph.h>
37
38namespace ogdf {
39
52template<typename T, template<typename P, class C> class H = PairingHeap>
53class Dijkstra {
54protected:
56
57public:
60
70 void callUnbound(const Graph& G, const EdgeArray<T>& weight, const List<node>& sources,
71 NodeArray<edge>& predecessor, NodeArray<T>& distance, bool directed = false,
72 bool arcsReversed = false) {
74 distance.init(G, std::numeric_limits<T>::max());
75 predecessor.init(G, nullptr);
76
77#ifdef OGDF_DEBUG
78 // No source should be given multiple times.
79 NodeArray<bool> isSource {G, false};
80 for (node s : sources) {
81 OGDF_ASSERT(!isSource[s]);
82 isSource[s] = true;
83 }
84#endif
85
86 // initialization
87 for (node v : G.nodes) {
88 queue.push(v, distance[v]);
89 }
90 for (node s : sources) {
91 queue.decrease(s, (distance[s] = 0));
92 }
93
94#ifdef OGDF_DEBUG
95 for (edge de : G.edges) {
96 OGDF_ASSERT(weight[de] >= 0);
97 }
98#endif
99
100 while (!queue.empty()) {
101 node v = queue.topElement();
102 queue.pop();
103 if (!predecessor[v]
104 && m_eps.greater(distance[v], static_cast<T>(0))) { // v is unreachable, ignore
105 continue;
106 }
110 if (directed
111 && ((!arcsReversed && e->target() == v)
112 || (arcsReversed && e->target() != v))) {
113 continue;
114 }
115
116 if (m_eps.greater(distance[w], distance[v] + weight[e])) {
117 OGDF_ASSERT(std::numeric_limits<T>::max() - weight[e] >= distance[v]);
118 queue.decrease(w, (distance[w] = distance[v] + weight[e]));
119 predecessor[w] = e;
120 }
121 }
122 }
123 }
124
126
138 void callBound(const Graph& G, const EdgeArray<T>& weight, const List<node>& sources,
139 NodeArray<edge>& predecessor, NodeArray<T>& distance, bool directed, bool arcsReversed,
140 node target, T maxLength = std::numeric_limits<T>::max()) {
142 distance.init(G, std::numeric_limits<T>::max());
143 predecessor.init(G, nullptr);
144
145 // initialization
146 for (node s : sources) {
147 queue.push(s, (distance[s] = 0));
148 }
149
150#ifdef OGDF_DEBUG
151 for (edge de : G.edges) {
152 OGDF_ASSERT(weight[de] >= 0);
153 }
154#endif
155
156 while (!queue.empty()) {
157 node v = queue.topElement();
158 if (v == target) { // terminate early if this is our sole target
159 break;
160 }
161
162 queue.pop();
163 if (!predecessor[v]
164 && m_eps.greater(distance[v], static_cast<T>(0))) { // v is unreachable, ignore
165 continue;
166 }
170 if (directed
171 && ((!arcsReversed && e->target() == v)
172 || (arcsReversed && e->target() != v))) {
173 continue;
174 }
175
176 const T newDistance = distance[v] + weight[e];
178 // using this edge would result in a path length greater than our upper bound
179 continue;
180 }
181 if (m_eps.greater(distance[w], newDistance)) {
182 OGDF_ASSERT(std::numeric_limits<T>::max() - weight[e] >= distance[v]);
183 distance[w] = newDistance;
184 if (queue.contains(w)) {
185 queue.decrease(w, distance[w]);
186 } else {
187 queue.push(w, distance[w]);
188 }
189 predecessor[w] = e;
190 }
191 }
192 }
193 }
194
197
207 void callUnbound(const Graph& G, const EdgeArray<T>& weight, node s, NodeArray<edge>& predecessor,
208 NodeArray<T>& distance, bool directed = false, bool arcsReversed = false) {
210 sources.pushBack(s);
211 callUnbound(G, weight, sources, predecessor, distance, directed, arcsReversed);
212 }
213
215
226 void callBound(const Graph& G, const EdgeArray<T>& weight, node s, NodeArray<edge>& predecessor,
227 NodeArray<T>& distance, bool directed, bool arcsReversed, node target,
228 T maxLength = std::numeric_limits<T>::max()) {
230 sources.pushBack(s);
231 callBound(G, weight, sources, predecessor, distance, directed, arcsReversed, target,
232 maxLength);
233 }
234
236
246 void call(const Graph& G, const EdgeArray<T>& weight, const List<node>& sources,
247 NodeArray<edge>& predecessor, NodeArray<T>& distance, bool directed = false,
248 bool arcsReversed = false, node target = nullptr,
249 T maxLength = std::numeric_limits<T>::max()) {
250 if (target == nullptr && maxLength == std::numeric_limits<T>::max()) {
251 callUnbound(G, weight, sources, predecessor, distance, directed, arcsReversed);
252 } else {
253 callBound(G, weight, sources, predecessor, distance, directed, arcsReversed, target,
254 maxLength);
255 }
256 }
257
259
269 void call(const Graph& G, const EdgeArray<T>& weight, const node s, NodeArray<edge>& predecessor,
270 NodeArray<T>& distance, bool directed = false, bool arcsReversed = false,
271 node target = nullptr, T maxLength = std::numeric_limits<T>::max()) {
272 if (target == nullptr && maxLength == std::numeric_limits<T>::max()) {
273 callUnbound(G, weight, s, predecessor, distance, directed, arcsReversed);
274 } else {
275 callBound(G, weight, s, predecessor, distance, directed, arcsReversed, target, maxLength);
276 }
277 }
278};
279
280}
Compare floating point numbers with epsilons and integral numbers with normal compare operators.
Includes declaration of graph class.
Priority queue interface wrapping various heaps.
Definition Graph_d.h:79
Dijkstra's single source shortest path algorithm.
Definition Dijkstra.h:53
void call(const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false, node target=nullptr, T maxLength=std::numeric_limits< T >::max())
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths a...
Definition Dijkstra.h:246
void callUnbound(const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false)
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths a...
Definition Dijkstra.h:70
void callUnbound(const Graph &G, const EdgeArray< T > &weight, node s, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false)
Calculates, based on the graph G with corresponding edge costs and a source node s,...
Definition Dijkstra.h:207
void call(const Graph &G, const EdgeArray< T > &weight, const node s, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false, node target=nullptr, T maxLength=std::numeric_limits< T >::max())
Calculates, based on the graph G with corresponding edge costs and a source node s,...
Definition Dijkstra.h:269
void callBound(const Graph &G, const EdgeArray< T > &weight, node s, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed, bool arcsReversed, node target, T maxLength=std::numeric_limits< T >::max())
Calculates, based on the graph G with corresponding edge costs and a source node s,...
Definition Dijkstra.h:226
void callBound(const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed, bool arcsReversed, node target, T maxLength=std::numeric_limits< T >::max())
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths a...
Definition Dijkstra.h:138
EpsilonTest m_eps
For floating point comparisons (if floating point is used)
Definition Dijkstra.h:55
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
node target() const
Returns the target node of the edge.
Definition Graph_d.h:338
std::enable_if< std::is_integral< T >::value, bool >::type greater(const T &x, const T &y) const
Compare if x is GREATER than y for integral types.
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1531
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
void init()
Reinitializes the array. Associates the array with no graph.
Definition NodeArray.h:266
Class for the representation of nodes.
Definition Graph_d.h:177