Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
bounded_dijkstra.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_GRAPH_BOUNDED_DIJKSTRA_H_
15#define OR_TOOLS_GRAPH_BOUNDED_DIJKSTRA_H_
16
17#include <algorithm>
18#include <cstddef>
19#include <functional>
20#include <limits>
21#include <type_traits>
22#include <utility>
23#include <vector>
24
25#include "absl/algorithm/container.h"
26#include "absl/base/attributes.h"
27#include "absl/log/check.h"
28#include "absl/types/span.h"
32#include "ortools/base/top_n.h"
33#include "ortools/graph/graph.h"
34
35namespace operations_research {
36
37// Computes a shortest path from source to destination in a weighted directed
38// graph, specified as an arc list.
39//
40// This function also demonstrates how to use the more feature rich
41// BoundedDijkstraWrapper (defined below) in the simple case, see the
42// implementation at the bottom of this file.
43//
44// We take a sparse directed input graph with nodes indexed in [0, num_nodes).
45// Each arcs goes from a tail node to a head node (tail -> head) and must have a
46// NON-NEGATIVE length. Self-arc or duplicate arcs are supported. This is
47// provided as 3 parallel vectors of the same size. Note that we validate the
48// input consistency with checks.
49//
50// If your graph is undirected, you can easily transform it by adding two arcs
51// (a -> b and b -> a) for each edge (a <-> b).
52//
53// This returns a pair (path length, node-path from source to destination)
54// corresponding to a shortest path. Both source and destination will be
55// included in the path.
56//
57// If destination is not reachable from source, or if the shortest path length
58// is >= limit we will return {limit, {}}. As a consequence any arc length >=
59// limit is the same as no arc. The code is also overflow-safe and will behave
60// correctly if the limit is int64max or infinity.
61template <typename NodeIndex, typename DistanceType>
62std::pair<DistanceType, std::vector<NodeIndex>> SimpleOneToOneShortestPath(
63 NodeIndex source, NodeIndex destination, absl::Span<const NodeIndex> tails,
64 absl::Span<const NodeIndex> heads, absl::Span<const DistanceType> lengths,
65 DistanceType limit = std::numeric_limits<DistanceType>::max());
66
67namespace internal {
68
69// TODO(user): We should move `is_strong_int` to util/intops/strong_int.h.
70template <typename T>
71struct is_strong_int : std::false_type {};
72
73template <typename Tag, typename Native, typename Validator>
74struct is_strong_int<::util_intops::StrongInt<Tag, Native, Validator>>
75 : std::true_type {};
76
77template <typename IndexType, typename ValueType>
79 std::conditional_t<is_strong_int<IndexType>::value,
81 std::vector<ValueType>>;
82
83template <class T, typename ArcIndex>
85 public:
86 explicit ElementGetter(const IndexedVector<ArcIndex, T>& c) : c_(c) {}
87 const T& operator()(ArcIndex index) const { return c_[index]; }
88
89 private:
91};
92
93} // namespace internal
94
95// A wrapper that holds the memory needed to run many bounded shortest path
96// computations on the given graph. The graph must implement the
97// interface described in graph.h (without the need for reverse arcs).
98//
99// We use the length and distance formalism here, but the arc lengths can
100// represent any numeric physical quantity. A shortest path will just be a path
101// minimizing this quantity. Arc length MUST be non-negative though. The code
102// should work with both signed and unsigned integer, or floating point
103// DistanceType.
104//
105// If one do not use source/destination distance offset, this class is
106// integer-overflow safe, and one can safely use distance_limit =
107// std::numeric_limits<int64_t>::max() for instance. Any arcs with a distance >=
108// distance_limit will then be the same as a non-existent arc.
109//
110// With source/destination offsets, the potential integer overflow situation is
111// trickier: one need to make sure that the range (distance_limit -
112// source_offset) do not overflow in case of negative source_offset. And also
113// that (distance_limit + destination_offset) do not overflow. Note that with
114// negative source_offset, arc with a length greater than the distance_limit can
115// still be considered!
116template <class GraphType, class DistanceType,
117 class ArcLengthFunctor = internal::ElementGetter<
118 DistanceType, typename GraphType::ArcIndex>>
120 public:
121 typedef typename GraphType::NodeIndex NodeIndex;
122 typedef typename GraphType::ArcIndex ArcIndex;
123 typedef DistanceType distance_type;
124
125 // A vector of T, indexed by NodeIndex/ArcIndex.
126 template <typename T>
128 template <typename T>
130
131 // IMPORTANT: Both arguments must outlive the class. The arc lengths cannot be
132 // negative and the vector must be of the correct size (both preconditions are
133 // CHECKed).
134 //
135 // SUBTLE: The client can modify the graph and the arc length between calls to
136 // RunBoundedDijkstra(). That's fine. Doing so will obviously invalidate the
137 // reader API of the last Dijkstra run, which could return junk, or crash.
138 BoundedDijkstraWrapper(const GraphType* graph,
140
141 // Variant that takes a custom arc length functor and copies it locally.
142 BoundedDijkstraWrapper(const GraphType* graph,
143 ArcLengthFunctor arc_length_functor);
144
145 // The typical Dijkstra, from a single source with distance zero, to all nodes
146 // of the graph within the distance limit (exclusive). The first element of
147 // the returned vector will always be the source_node with a distance of zero.
148 // See RunBoundedDijkstraFromMultipleSources() for more information.
149 const std::vector<NodeIndex>& RunBoundedDijkstra(
150 NodeIndex source_node, DistanceType distance_limit) {
151 return RunBoundedDijkstraFromMultipleSources({{source_node, 0}},
152 distance_limit);
153 }
154
155 // Finds the shortest path between two nodes, subject to the distance limit.
156 // Returns true iff it exists and its length is < distance_limit.
157 //
158 // If this returns true, you can get the path distance with distances()[to]
159 // and the path with ArcPathTo(to) or NodePathTo(to).
161 DistanceType distance_limit);
162
163 // Returns the list of all the nodes which are under the given distance limit
164 // (exclusive) from at least one of the given source nodes (which also have
165 // an initial distance offset, to be added to the distance).
166 // The nodes are sorted by increasing distance.
167 // By "distance", we mean the length of the shortest path from any source
168 // plus the source's distance offset, where the length of a path is the
169 // sum of the length of its arcs
170 const std::vector<NodeIndex>& RunBoundedDijkstraFromMultipleSources(
171 const std::vector<std::pair<NodeIndex, DistanceType>>&
172 sources_with_distance_offsets,
173 DistanceType distance_limit);
174
175 // Like RunBoundedDijkstraFromMultipleSources(), but this one stops as soon as
176 // it has determined the shortest path from any of the sources to the closest
177 // "num_destinations_to_reach" destinations, and returns those destinations,
178 // sorted by overall distance (also counting the destination offsets).
179 //
180 // If num_destinations_to_reach is non-positive, returns the empty vector, if
181 // it is greater than the number of distinct destination nodes, it has no
182 // effect (it's safe to do so).
183 //
184 // If the limit is reached before, the returned vector may have smaller size,
185 // in particular it may be empty if none of the destinations was reachable.
186 //
187 // Both the sources and the destinations have a "distance offset", which is
188 // added to the path length to determine the distance between them.
189 //
190 // The rest of the reader API below is available; with the caveat that you
191 // should only try to access the nodes that have been reached by the search.
192 // That's true for the returned node index (if not -1) and its ancestors.
193 //
194 // Note that the distances() will take the source offsets into account,
195 // but not the destination offsets.
196 std::vector<NodeIndex>
198 const std::vector<std::pair<NodeIndex, DistanceType>>&
199 sources_with_distance_offsets,
200 const std::vector<std::pair<NodeIndex, DistanceType>>&
201 destinations_with_distance_offsets,
202 int num_destinations_to_reach, DistanceType distance_limit);
203
204 // Like RunBoundedDijkstraFromMultipleSources(), but will call a user-provided
205 // callback "settled_node_callback" when settling each node ('settling' a node
206 // happens at most once per node, when popping it from the Dijkstra queue,
207 // meaning that the node has been fully 'processed'). This callback may modify
208 // the distance limit dynamically, thus affecting the stopping criterion.
209 const std::vector<NodeIndex>& RunBoundedDijkstraWithSettledNodeCallback(
210 const std::vector<std::pair<NodeIndex, DistanceType>>&
211 sources_with_distance_offsets,
212 std::function<void(NodeIndex settled_node, DistanceType settled_distance,
213 DistanceType* distance_limit)>
214 settled_node_callback,
215 DistanceType distance_limit);
216
217 // Returns true if `node` was reached by the last Run*() call.
218 bool IsReachable(NodeIndex node) const { return is_reached_[node]; }
219
220 // Returns all the reached nodes form the previous Run*() call.
221 const ByNode<NodeIndex>& reached_nodes() const { return reached_nodes_; }
222
223 // The following vectors are all indexed by graph node indices.
224 //
225 // IMPORTANT: after each Run*() function, only the positions of the
226 // reached nodes are updated, the others will contain junk.
227
228 // The distance of the nodes from their source.
229 const ByNode<DistanceType>& distances() const { return distances_; }
230
231 // The parent of the nodes in the shortest path from their source.
232 // When a node doesn't have any parent (it has to be a source), its parent
233 // is itself.
234 // Note that a path will never contain the same node twice, even if some
235 // arcs have a length of zero.
236 // Note also that some sources may have parents, because of the initial
237 // distances.
238 const ByNode<NodeIndex>& parents() const { return parents_; }
239
240 // The arc reaching a given node in the path from their source.
241 // arc_from_source()[x] is undefined (i.e. junk) when parents()[x] == x.
242 const ByNode<ArcIndex>& arc_from_source() const { return arc_from_source_; }
243
244 // Returns the list of all the arcs in the shortest path from the node's
245 // source to the node.
246 std::vector<ArcIndex> ArcPathTo(NodeIndex node) const;
247
248 ABSL_DEPRECATED("Use ArcPathTo() instead.")
249 std::vector<ArcIndex> ArcPathToNode(NodeIndex node) const {
250 return ArcPathTo(node);
251 }
252
253 // Returns the list of all the nodes in the shortest path from the node's
254 // source to the node. This always start by the node's source, and end by
255 // the given node. In the case that source == node, returns {node}.
256 std::vector<NodeIndex> NodePathTo(NodeIndex node) const;
257
258 // Returns the node's source. This is especially useful when running
259 // Dijkstras from multiple sources.
261
262 // Original Source/Destination index extraction, after a call to the
263 // multi-source and/or multi-destination variants:
264 // Retrieves the original index of the source or destination node in the
265 // source/destination lists given in the method calls. Eg. if you called
266 // RunBoundedDijkstraFromMultipleSourcesToMultipleDestinations(srcs, dsts),
267 // then srcs[GetSourceIndex(node)] = (node, ...), for all "node" that appear
268 // in "srcs". Ditto for dsts and GetDestinationIndex().
269 //
270 // If the node was listed several times as a source (or destinations), it'll
271 // pick the listing with the smallest distance offset.
272 // If the node is not a source (or destination), this returns junk: you can't
273 // rely on the value.
274 //
275 // These methods are invalidated by the next RunBoundedDijkstra*() call.
276 int GetSourceIndex(NodeIndex node) const;
277 int GetDestinationIndex(NodeIndex node) const;
278
279 // Trivial accessors to the underlying graph and arc lengths.
280 const GraphType& graph() const { return *graph_; }
282 CHECK(arc_lengths_);
283 return *arc_lengths_;
284 }
285 DistanceType GetArcLength(ArcIndex arc) const {
286 const DistanceType length = arc_length_functor_(arc);
287 DCHECK_GE(length, 0);
288 return length;
289 }
290
291 private:
292 // The default copy constructor is problematic in a multi-threaded
293 // environment.
295
296 // The Graph and length of each arc.
297 const GraphType* const graph_;
298 ArcLengthFunctor arc_length_functor_;
299 const ByArc<DistanceType>* const arc_lengths_;
300
301 // Data about the last Dijkstra run.
302 ByNode<DistanceType> distances_;
303 ByNode<NodeIndex> parents_;
304 ByNode<ArcIndex> arc_from_source_;
305 ByNode<bool> is_reached_;
306 std::vector<NodeIndex> reached_nodes_;
307
308 // Priority queue of nodes, ordered by their distance to the source.
309 struct NodeDistance {
310 NodeIndex node; // The target node.
311 DistanceType distance; // Its distance from the source.
312
313 bool operator<(const NodeDistance& other) const {
314 // PERFORMANCE(user): Here are some versions of the comparison operator:
315 // 0) distance != other.distance ? distance < other.distance
316 // : node < other.node
317 // 1) Same, with ABSL_PREDICT_TRUE() around the first test.
318 // 2) std::tie(distance, node) < std::tie(other.distance, other.node)
319 // 3) __int128 comparison with *reinterpret_cast<const __int128*>(this).
320 // (note: this only works when the node and distance types are integer
321 // or ieee754 floating-point, when the machine is little endian, and
322 // when the total size of NodeDistance equals 16 bytes).
323 // And here are the speeds of the BM_GridGraph benchmark (in which
324 // DistanceType=int64_t and NodeIndex=int32_t), done with benchy
325 // --runs=20: 0) BM_GridGraph<true> 9.22ms ± 5% BM_GridGraph<false> 3.19ms
326 // ± 6% 1) BM_GridGraph<true> 8.89ms ± 4% BM_GridGraph<false> 3.07ms ±
327 // 3% 2) BM_GridGraph<true> 8.61ms ± 3% BM_GridGraph<false> 3.13ms ± 6%
328 // 3) BM_GridGraph<true> 7.85ms ± 2% BM_GridGraph<false> 3.29ms ± 2%
329 return std::tie(distance, node) < std::tie(other.distance, other.node);
330 }
331 bool operator>(const NodeDistance& other) const { return other < *this; }
332 };
333 std::vector<NodeDistance> queue_;
334
335 // These are used by some of the Run...() variants, and are kept as data
336 // members to avoid reallocation upon multiple calls.
337 // The vectors are only allocated after they are first used.
338 // Between calls, is_destination_ is all false, and the rest is junk.
339 std::vector<bool> is_destination_;
340 ByNode<int> node_to_source_index_;
341 ByNode<int> node_to_destination_index_;
342};
343
344// -----------------------------------------------------------------------------
345// Implementation.
346// -----------------------------------------------------------------------------
347
348template <class GraphType, class DistanceType, class ArcLengthFunctor>
350 BoundedDijkstraWrapper(const GraphType* graph,
352 : graph_(graph),
353 arc_length_functor_(*arc_lengths),
354 arc_lengths_(arc_lengths) {
355 CHECK(arc_lengths_ != nullptr);
356 CHECK_EQ(ArcIndex(arc_lengths_->size()), graph->num_arcs());
357 for (const DistanceType length : *arc_lengths) {
358 CHECK_GE(length, 0);
359 }
360}
361
362template <class GraphType, class DistanceType, class ArcLengthFunctor>
364 BoundedDijkstraWrapper(const GraphType* graph,
365 ArcLengthFunctor arc_length_functor)
366 : graph_(graph),
367 arc_length_functor_(std::move(arc_length_functor)),
368 arc_lengths_(nullptr) {}
369
370template <class GraphType, class DistanceType, class ArcLengthFunctor>
373 : graph_(other.graph_),
374 arc_length_functor_(other.arc_length_functor_),
375 arc_lengths_(other.arc_lengths_) {}
376
377template <class GraphType, class DistanceType, class ArcLengthFunctor>
378const std::vector<typename GraphType::NodeIndex>&
381 const std::vector<std::pair<NodeIndex, DistanceType>>&
382 sources_with_distance_offsets,
383 DistanceType distance_limit) {
385 sources_with_distance_offsets, nullptr, distance_limit);
386}
387
388template <class GraphType, class DistanceType, class ArcLengthFunctor>
389std::vector<typename GraphType::NodeIndex>
392 const std::vector<std::pair<NodeIndex, DistanceType>>&
393 sources_with_distance_offsets,
394 const std::vector<std::pair<NodeIndex, DistanceType>>&
395 destinations_with_distance_offsets,
396 int num_destinations_to_reach, DistanceType distance_limit) {
397 if (destinations_with_distance_offsets.empty()) return {};
398 if (num_destinations_to_reach <= 0) return {};
399
400 // Initialize the destinations. We'll adapt the distance limit according to
401 // the minimal destination distance offset. This is an optional optimization,
402 // to reduce the search space.
403 DCHECK_GE(num_destinations_to_reach, 0);
404 int num_destinations = 0;
405 is_destination_.resize(static_cast<size_t>(graph_->num_nodes()), false);
406 node_to_destination_index_.resize(graph_->num_nodes(), -1);
407 DistanceType min_destination_distance_offset =
408 destinations_with_distance_offsets[0].second;
409 for (int i = 0; i < destinations_with_distance_offsets.size(); ++i) {
410 const NodeIndex node = destinations_with_distance_offsets[i].first;
411 const DistanceType distance = destinations_with_distance_offsets[i].second;
412 if (!is_destination_[static_cast<size_t>(node)]) ++num_destinations;
413 // Skip useless repetitions.
414 if (is_destination_[static_cast<size_t>(node)] &&
415 distance >=
416 destinations_with_distance_offsets[node_to_destination_index_[node]]
417 .second) {
418 continue;
419 }
420 is_destination_[static_cast<size_t>(node)] = true;
421 node_to_destination_index_[node] = i;
422 min_destination_distance_offset =
423 std::min(min_destination_distance_offset, distance);
424 }
425 distance_limit -= min_destination_distance_offset;
426 if (num_destinations_to_reach > num_destinations) {
427 num_destinations_to_reach = num_destinations;
428 }
430 /*limit=*/num_destinations_to_reach);
431
432 std::function<void(NodeIndex, DistanceType, DistanceType*)>
433 settled_node_callback =
434 [this, num_destinations_to_reach, min_destination_distance_offset,
435 &destinations_with_distance_offsets, &closest_destinations](
436 NodeIndex settled_node, DistanceType settled_distance,
437 DistanceType* distance_limit) {
438 if (!is_destination_[static_cast<size_t>(settled_node)]) return;
439 const DistanceType distance =
440 settled_distance +
441 destinations_with_distance_offsets
442 [node_to_destination_index_[settled_node]]
443 .second -
444 min_destination_distance_offset;
445 if (distance >= *distance_limit) return;
446 closest_destinations.push(NodeDistance{settled_node, distance});
447 if (closest_destinations.size() == num_destinations_to_reach) {
448 const DistanceType new_distance_limit =
449 closest_destinations.peek_bottom().distance;
450 DCHECK_LE(new_distance_limit, *distance_limit);
451 *distance_limit = new_distance_limit;
452 }
453 };
454
456 sources_with_distance_offsets, settled_node_callback, distance_limit);
457
458 // Clean up, sparsely, for the next call.
459 for (const auto& [node, _] : destinations_with_distance_offsets) {
460 is_destination_[static_cast<size_t>(node)] = false;
461 }
462
463 // Return the closest "num_destinations_to_reach" reached destinations,
464 // sorted by distance.
465 std::vector<NodeIndex> sorted_destinations;
466 sorted_destinations.reserve(closest_destinations.size());
467 for (const NodeDistance& d : closest_destinations.Take()) {
468 sorted_destinations.push_back(d.node);
469 }
470 return sorted_destinations;
471}
472
473template <class GraphType, class DistanceType, class ArcLengthFunctor>
476 DistanceType distance_limit) {
477 bool reached = false;
478 std::function<void(NodeIndex, DistanceType, DistanceType*)>
479 settled_node_callback = [to, &reached](NodeIndex node,
480 DistanceType distance,
481 DistanceType* distance_limit) {
482 if (node != to) return;
483 if (distance >= *distance_limit) return;
484 reached = true;
485 // Stop the search, by setting the distance limit to 0.
486 *distance_limit = 0;
487 };
488 RunBoundedDijkstraWithSettledNodeCallback({{from, 0}}, settled_node_callback,
489 distance_limit);
490 return reached;
491}
492
493template <class GraphType, class DistanceType, class ArcLengthFunctor>
494const std::vector<typename GraphType::NodeIndex>&
497 const std::vector<std::pair<NodeIndex, DistanceType>>&
498 sources_with_distance_offsets,
499 std::function<void(NodeIndex settled_node,
500 DistanceType settled_distance,
501 DistanceType* distance_limit)>
502 settled_node_callback,
503 DistanceType distance_limit) {
504 // Sparse clear is_reached_ from the last call.
505 for (const NodeIndex node : reached_nodes_) {
506 is_reached_[node] = false;
507 }
508 reached_nodes_.clear();
509 DCHECK(!absl::c_linear_search(is_reached_, true));
510
511 is_reached_.resize(graph_->num_nodes(), false);
512 distances_.resize(graph_->num_nodes(), distance_limit);
513 parents_.resize(graph_->num_nodes(), std::numeric_limits<NodeIndex>::min());
514 arc_from_source_.resize(graph_->num_nodes(), GraphType::kNilArc);
515
516 // Initialize sources.
517 CHECK(queue_.empty());
518 node_to_source_index_.resize(graph_->num_nodes(), -1);
519 for (int i = 0; i < sources_with_distance_offsets.size(); ++i) {
520 const NodeIndex node = sources_with_distance_offsets[i].first;
521 DCHECK_GE(node, NodeIndex(0));
522 DCHECK_LT(node, graph_->num_nodes());
523 const DistanceType distance = sources_with_distance_offsets[i].second;
524 // Sources with an initial distance ≥ limit are *not* reached.
525 if (distance >= distance_limit) continue;
526 // Skip useless repetitions.
527 if (is_reached_[node] && distance >= distances_[node]) continue;
528 if (!is_reached_[node]) {
529 is_reached_[node] = true;
530 reached_nodes_.push_back(node);
531 parents_[node] = node; // Set the parent to itself.
532 }
533 node_to_source_index_[node] = i;
534 distances_[node] = distance;
535 }
536 for (const NodeIndex source : reached_nodes_) {
537 queue_.push_back({source, distances_[source]});
538 }
539 std::make_heap(queue_.begin(), queue_.end(), std::greater<NodeDistance>());
540
541 // Dijkstra loop.
542 while (!queue_.empty()) {
543 const NodeDistance top = queue_.front();
544 std::pop_heap(queue_.begin(), queue_.end(), std::greater<NodeDistance>());
545 queue_.pop_back();
546
547 // The queue may contain the same node more than once, skip irrelevant
548 // entries.
549 if (distances_[top.node] < top.distance) continue;
550
551 if (settled_node_callback) {
552 // We usually never enqueue anything >= distance_limit, but if
553 // settled_node_callback is not nullptr, the limit might have been changed
554 // after the enqueue were done. So we re-test it here to make sure we
555 // never call the callback on such node.
556 if (top.distance < distance_limit) {
557 settled_node_callback(top.node, top.distance, &distance_limit);
558 }
559
560 // If we are over the distance, we can empty the queue and abort.
561 if (top.distance >= distance_limit) {
562 queue_.clear();
563 break;
564 }
565 } else {
566 DCHECK_LT(top.distance, distance_limit);
567 }
568
569 // Visit the neighbors.
570 const DistanceType limit = distance_limit - top.distance;
571 for (const typename GraphType::ArcIndex arc :
572 graph_->OutgoingArcs(top.node)) {
573 // Overflow-safe check of top.distance + arc_length >= distance_limit.
574 // This works since we know top.distance < distance_limit, as long as we
575 // don't have negative top.distance (which might happen with negative
576 // source offset). Note that for floating point, it is not exactly the
577 // same as (top_distance + arc_length < distance_limit) though.
578 const DistanceType arc_length = GetArcLength(arc);
579 if (arc_length >= limit) continue;
580 const DistanceType candidate_distance = top.distance + arc_length;
581
582 const NodeIndex head = graph_->Head(arc);
583 if (is_reached_[head]) {
584 if (candidate_distance >= distances_[head]) continue;
585 } else {
586 is_reached_[head] = true;
587 reached_nodes_.push_back(head);
588 }
589 distances_[head] = candidate_distance;
590 parents_[head] = top.node;
591 arc_from_source_[head] = arc;
592 queue_.push_back({head, candidate_distance});
593 std::push_heap(queue_.begin(), queue_.end(),
594 std::greater<NodeDistance>());
595 }
596 }
597
598 return reached_nodes_;
599}
600
601template <class GraphType, class DistanceType, class ArcLengthFunctor>
602std::vector<typename GraphType::ArcIndex>
604 NodeIndex node) const {
605 std::vector<typename GraphType::ArcIndex> output;
606 int loop_detector = 0;
607 while (true) {
608 DCHECK_GE(node, NodeIndex(0));
609 DCHECK_LT(node, NodeIndex(parents_.size()));
610 CHECK_LT(loop_detector++, parents_.size());
611 if (parents_[node] == node) break;
612 output.push_back(arc_from_source_[node]);
613 node = parents_[node];
614 }
615 std::reverse(output.begin(), output.end());
616 return output;
617}
618
619template <class GraphType, class DistanceType, class ArcLengthFunctor>
620std::vector<typename GraphType::NodeIndex>
622 NodeIndex node) const {
623 std::vector<NodeIndex> output;
624 int loop_detector = 0;
625 while (true) {
626 DCHECK_GE(node, NodeIndex(0));
627 DCHECK_LT(node, NodeIndex(parents_.size()));
628 CHECK_LT(loop_detector++, parents_.size());
629 output.push_back(node);
630 if (parents_[node] == node) break;
631 node = parents_[node];
632 }
633 std::reverse(output.begin(), output.end());
634 return output;
635}
636
637template <class GraphType, class DistanceType, class ArcLengthFunctor>
638typename GraphType::NodeIndex BoundedDijkstraWrapper<
639 GraphType, DistanceType,
640 ArcLengthFunctor>::SourceOfShortestPathToNode(NodeIndex node) const {
641 NodeIndex parent = node;
642 while (parents_[parent] != parent) parent = parents_[parent];
643 return parent;
644}
645
646template <class GraphType, class DistanceType, class ArcLengthFunctor>
647int BoundedDijkstraWrapper<GraphType, DistanceType,
648 ArcLengthFunctor>::GetSourceIndex(NodeIndex node)
649 const {
650 DCHECK_GE(node, NodeIndex(0));
651 DCHECK_LT(node, NodeIndex(node_to_source_index_.size()));
652 return node_to_source_index_[node];
653}
654
655template <class GraphType, class DistanceType, class ArcLengthFunctor>
658 DCHECK_GE(node, NodeIndex(0));
659 DCHECK_LT(node, NodeIndex(node_to_destination_index_.size()));
660 return node_to_destination_index_[node];
661}
662
663// -----------------------------------------------------------------------------
664// Example usage.
665// -----------------------------------------------------------------------------
666
667template <typename NodeIndex, typename DistanceType>
668std::pair<DistanceType, std::vector<NodeIndex>> SimpleOneToOneShortestPath(
669 NodeIndex source, NodeIndex destination, absl::Span<const NodeIndex> tails,
670 absl::Span<const NodeIndex> heads, absl::Span<const DistanceType> lengths,
671 DistanceType limit) {
672 using ArcIndex = NodeIndex;
673 // Compute the number of nodes.
674 //
675 // This is not necessary, but is a good practice to allocate the graph size in
676 // one go. We also do some basic validation.
677 CHECK_GE(source, 0);
678 CHECK_GE(destination, 0);
679 NodeIndex num_nodes = std::max(source + 1, destination + 1);
680 for (const NodeIndex tail : tails) {
681 CHECK_GE(tail, 0);
682 num_nodes = std::max(tail + 1, num_nodes);
683 }
684 for (const NodeIndex head : heads) {
685 CHECK_GE(head, 0);
686 num_nodes = std::max(head + 1, num_nodes);
687 }
688
689 // The number of arcs.
690 const ArcIndex num_arcs = tails.size();
691 CHECK_EQ(num_arcs, heads.size());
692 CHECK_EQ(num_arcs, lengths.size());
693
694 // Build the graph. Note that this permutes arc indices for speed, but we
695 // don't care here since we will return a node path.
696 util::StaticGraph<NodeIndex, ArcIndex> graph(num_nodes, num_arcs);
697 std::vector<DistanceType> arc_lengths(lengths.begin(), lengths.end());
698 for (ArcIndex a = 0; a < num_arcs; ++a) {
699 // Negative length can cause the algo to loop forever and/or use a lot of
700 // memory. So it should be validated.
701 CHECK_GE(lengths[a], 0);
702 graph.AddArc(tails[a], heads[a]);
703 }
704 std::vector<int> permutation;
705 graph.Build(&permutation);
706 util::Permute(permutation, &arc_lengths);
707
708 // Compute a shortest path.
709 // This should work for both float/double or integer distances.
710 BoundedDijkstraWrapper<util::StaticGraph<>, DistanceType> wrapper(
711 &graph, &arc_lengths);
712 if (!wrapper.OneToOneShortestPath(source, destination, limit)) {
713 // No path exists, or shortest_distance >= limit.
714 return {limit, {}};
715 }
716
717 // A path exist, returns it.
718 return {wrapper.distances()[destination], wrapper.NodePathTo(destination)};
719}
720
721} // namespace operations_research
722
723#endif // OR_TOOLS_GRAPH_BOUNDED_DIJKSTRA_H_
const ByArc< DistanceType > & arc_lengths() const
std::vector< ArcIndex > ArcPathToNode(NodeIndex node) const
const GraphType & graph() const
Trivial accessors to the underlying graph and arc lengths.
const ByNode< ArcIndex > & arc_from_source() const
bool IsReachable(NodeIndex node) const
Returns true if node was reached by the last Run*() call.
NodeIndex SourceOfShortestPathToNode(NodeIndex node) const
std::vector< NodeIndex > NodePathTo(NodeIndex node) const
std::vector< ArcIndex > ArcPathTo(NodeIndex node) const
const std::vector< NodeIndex > & RunBoundedDijkstra(NodeIndex source_node, DistanceType distance_limit)
const ByNode< DistanceType > & distances() const
The distance of the nodes from their source.
std::vector< NodeIndex > RunBoundedDijkstraFromMultipleSourcesToMultipleDestinations(const std::vector< std::pair< NodeIndex, DistanceType > > &sources_with_distance_offsets, const std::vector< std::pair< NodeIndex, DistanceType > > &destinations_with_distance_offsets, int num_destinations_to_reach, DistanceType distance_limit)
bool OneToOneShortestPath(NodeIndex from, NodeIndex to, DistanceType distance_limit)
BoundedDijkstraWrapper(const GraphType *graph, const ByArc< DistanceType > *arc_lengths)
const ByNode< NodeIndex > & reached_nodes() const
Returns all the reached nodes form the previous Run*() call.
DistanceType GetArcLength(ArcIndex arc) const
internal::IndexedVector< ArcIndex, T > ByArc
internal::IndexedVector< NodeIndex, T > ByNode
A vector of T, indexed by NodeIndex/ArcIndex.
const std::vector< NodeIndex > & RunBoundedDijkstraFromMultipleSources(const std::vector< std::pair< NodeIndex, DistanceType > > &sources_with_distance_offsets, DistanceType distance_limit)
const ByNode< NodeIndex > & parents() const
const std::vector< NodeIndex > & RunBoundedDijkstraWithSettledNodeCallback(const std::vector< std::pair< NodeIndex, DistanceType > > &sources_with_distance_offsets, std::function< void(NodeIndex settled_node, DistanceType settled_distance, DistanceType *distance_limit)> settled_node_callback, DistanceType distance_limit)
const T & operator()(ArcIndex index) const
ElementGetter(const IndexedVector< ArcIndex, T > &c)
End of the interface. Below is the implementation.
std::conditional_t< is_strong_int< IndexType >::value, ::util_intops::StrongVector< IndexType, ValueType >, std::vector< ValueType > > IndexedVector
In SWIG mode, we don't want anything besides these top-level includes.
BlossomGraph::NodeIndex NodeIndex
std::pair< DistanceType, std::vector< NodeIndex > > SimpleOneToOneShortestPath(NodeIndex source, NodeIndex destination, absl::Span< const NodeIndex > tails, absl::Span< const NodeIndex > heads, absl::Span< const DistanceType > lengths, DistanceType limit=std::numeric_limits< DistanceType >::max())
STL namespace.
void Permute(const IntVector &permutation, Array *array_to_permute)
Definition graph.h:1101
trees with all degrees equal to