Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
dag_shortest_path.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_DAG_SHORTEST_PATH_H_
15#define OR_TOOLS_GRAPH_DAG_SHORTEST_PATH_H_
16
17#include <cmath>
18#include <cstddef>
19#include <functional>
20#include <limits>
21#include <vector>
22
23#include "absl/algorithm/container.h"
24#include "absl/log/check.h"
25#include "absl/log/log.h"
26#include "absl/status/status.h"
27#include "absl/strings/str_format.h"
28#include "absl/types/span.h"
29
30namespace operations_research {
31// TODO(b/332475231): extend to non-floating lengths.
32// TODO(b/332476147): extend to allow for length functor.
33
34// This library provides a few APIs to compute the shortest path on a given
35// directed acyclic graph (DAG).
36//
37// In the DAG, multiple arcs between the same pair of nodes is allowed. However,
38// self-loop arcs are not allowed.
39//
40// Note that we use the length formalism here, but the arc lengths can represent
41// any numeric physical quantity. A shortest path will just be a path minimizing
42// this quantity where the length of a path is the sum of the length of its
43// arcs. An arc length can be negative, or +inf (indicating that it should not
44// be used). An arc length cannot be -inf or nan.
45
46// -----------------------------------------------------------------------------
47// Basic API.
48// -----------------------------------------------------------------------------
49
50// `from` and `to` should both be in [0, num_nodes).
51// If the length is +inf, then the arc should not be used.
52struct ArcWithLength {
53 int from = 0;
54 int to = 0;
55 double length = 0.0;
56};
58struct PathWithLength {
59 double length = 0.0;
60 // The returned arc indices points into the `arcs_with_length` passed to the
61 // function below.
62 std::vector<int> arc_path;
63 std::vector<int> node_path; // includes the source node.
64};
66// Returns {+inf, {}, {}} if there is no path of finite length from the source
67// to the destination. Dies if `arcs_with_length` has a cycle.
69 int num_nodes, absl::Span<const ArcWithLength> arcs_with_length, int source,
70 int destination);
71
72// Returns the k-shortest paths by increasing length. Returns fewer than k paths
73// if there are fewer than k paths from the source to the destination. Returns
74// {{+inf, {}, {}}} if there is no path of finite length from the source to the
75// destination. Dies if `arcs_with_length` has a cycle.
76std::vector<PathWithLength> KShortestPathsOnDag(
77 int num_nodes, absl::Span<const ArcWithLength> arcs_with_length, int source,
78 int destination, int path_count);
79
80// -----------------------------------------------------------------------------
81// Advanced API.
82// -----------------------------------------------------------------------------
83// A wrapper that holds the memory needed to run many shortest path computations
84// efficiently on the given DAG. One call of `RunShortestPathOnDag()` has time
85// complexity O(|E| + |V|) and space complexity O(|V|).
86// `GraphType` can use any of the interfaces defined in `util/graph/graph.h`.
87// `ArcLengthContainer` can be any container of doubles.
88template <class GraphType, typename ArcLengthContainer = std::vector<double>>
90 public:
91 using NodeIndex = typename GraphType::NodeIndex;
92 using ArcIndex = typename GraphType::ArcIndex;
93 using ArcLengths = ArcLengthContainer;
94
95 // IMPORTANT: All arguments must outlive the class.
96 //
97 // The vector of `arc_lengths` *must* be of size `graph.num_arcs()` and
98 // indexed the same way as in `graph`.
99 //
100 // You *must* provide a topological order. You can use
101 // `util::graph::FastTopologicalSort(graph)` to compute one if you don't
102 // already have one. An invalid topological order results in an upper bound
103 // for all shortest path computations. For maximum performance, you can
104 // further reindex the nodes under the topological order so that the memory
105 // access pattern is generally forward instead of random. For example, if the
106 // topological order for a graph with 4 nodes is [2,1,0,3], you can re-label
107 // the nodes 2, 1, and 0 to 0, 1, and 2 (and updates arcs accordingly).
108 //
109 // Validity of arcs and topological order are CHECKed if compiled in DEBUG
110 // mode.
111 //
112 // SUBTLE: You can modify the graph, the arc lengths or the topological order
113 // between calls to the `RunShortestPathOnDag()` function. That's fine. Doing
114 // so will obviously invalidate the result API of the last shortest path run,
115 // which could return an upper bound, junk, or crash.
116 ShortestPathsOnDagWrapper(const GraphType* graph,
117 const ArcLengths* arc_lengths,
118 absl::Span<const NodeIndex> topological_order);
119
120 // Computes the shortest path to all reachable nodes from the given sources.
121 // This must be called before any of the query functions below.
122 void RunShortestPathOnDag(absl::Span<const NodeIndex> sources);
123
124 // Returns true if `node` is reachable from at least one source, i.e., the
125 // length from at least one source is finite.
126 bool IsReachable(NodeIndex node) const;
127 const std::vector<NodeIndex>& reached_nodes() const { return reached_nodes_; }
128
129 // Returns the length of the shortest path from `node`'s source to `node`.
130 double LengthTo(NodeIndex node) const {
131 return length_from_sources_[static_cast<size_t>(node)];
132 }
133 std::vector<double> LengthTo() const { return length_from_sources_; }
135 // Returns the list of all the arcs in the shortest path from `node`'s
136 // source to `node`. CHECKs if the node is reachable.
137 std::vector<ArcIndex> ArcPathTo(NodeIndex node) const;
138
139 // Returns the list of all the nodes in the shortest path from `node`'s
140 // source to `node` (including the source). CHECKs if the node is reachable.
141 std::vector<NodeIndex> NodePathTo(NodeIndex node) const;
142
143 // Accessors to the underlying graph and arc lengths.
144 const GraphType& graph() const { return *graph_; }
145 const ArcLengths& arc_lengths() const { return *arc_lengths_; }
146
147 private:
148 static constexpr double kInf = std::numeric_limits<double>::infinity();
149 const GraphType* const graph_;
150 const ArcLengths* const arc_lengths_;
151 absl::Span<const NodeIndex> const topological_order_;
152
153 // Data about the last call of the RunShortestPathOnDag() function.
154 std::vector<double> length_from_sources_;
155 std::vector<ArcIndex> incoming_shortest_path_arc_;
156 std::vector<NodeIndex> reached_nodes_;
157};
158
159// A wrapper that holds the memory needed to run many k-shortest paths
160// computations efficiently on the given DAG. One call of
161// `RunKShortestPathOnDag()` has time complexity O(|E| + k|V|log(d)) where d is
162// the mean degree of the graph and space complexity O(k|V|).
163// `GraphType` can use any of the interfaces defined in `util/graph/graph.h`.
164// IMPORTANT: Only use if `path_count > 1` (k > 1) otherwise use
165// `ShortestPathsOnDagWrapper`.
166template <class GraphType, typename ArcLengthContainer = std::vector<double>>
168 public:
169 using NodeIndex = typename GraphType::NodeIndex;
170 using ArcIndex = typename GraphType::ArcIndex;
171 using ArcLengths = ArcLengthContainer;
172
173 // IMPORTANT: All arguments must outlive the class.
174 //
175 // The vector of `arc_lengths` *must* be of size `graph.num_arcs()` and
176 // indexed the same way as in `graph`.
177 //
178 // You *must* provide a topological order. You can use
179 // `util::graph::FastTopologicalSort(graph)` to compute one if you don't
180 // already have one. An invalid topological order results in an upper bound
181 // for all shortest path computations. For maximum performance, you can
182 // further reindex the nodes under the topological order so that the memory
183 // access pattern is generally forward instead of random. For example, if the
184 // topological order for a graph with 4 nodes is [2,1,0,3], you can re-label
185 // the nodes 2, 1, and 0 to 0, 1, and 2 (and updates arcs accordingly).
186 //
187 // Validity of arcs and topological order are CHECKed if compiled in DEBUG
188 // mode.
189 //
190 // SUBTLE: You can modify the graph, the arc lengths or the topological order
191 // between calls to the `RunKShortestPathOnDag()` function. That's fine. Doing
192 // so will obviously invalidate the result API of the last shortest path run,
193 // which could return an upper bound, junk, or crash.
194 KShortestPathsOnDagWrapper(const GraphType* graph,
195 const ArcLengths* arc_lengths,
196 absl::Span<const NodeIndex> topological_order,
197 int path_count);
198
199 // Computes the shortest path to all reachable nodes from the given sources.
200 // This must be called before any of the query functions below.
201 void RunKShortestPathOnDag(absl::Span<const NodeIndex> sources);
202
203 // Returns true if `node` is reachable from at least one source, i.e., the
204 // length of the shortest path from at least one source is finite.
205 bool IsReachable(NodeIndex node) const;
206 const std::vector<NodeIndex>& reached_nodes() const { return reached_nodes_; }
207
208 // Returns the lengths of the k-shortest paths from `node`'s source to `node`
209 // in increasing order. If there are less than k paths, return all path
210 // lengths.
211 std::vector<double> LengthsTo(NodeIndex node) const;
212
213 // Returns the list of all the arcs of the k-shortest paths from `node`'s
214 // source to `node`.
215 std::vector<std::vector<ArcIndex>> ArcPathsTo(NodeIndex node) const;
216
217 // Returns the list of all the nodes of the k-shortest paths from `node`'s
218 // source to `node` (including the source). CHECKs if the node is reachable.
219 std::vector<std::vector<NodeIndex>> NodePathsTo(NodeIndex node) const;
220
221 // Accessors to the underlying graph and arc lengths.
222 const GraphType& graph() const { return *graph_; }
223 const ArcLengths& arc_lengths() const { return *arc_lengths_; }
224 int path_count() const { return path_count_; }
225
226 private:
227 static constexpr double kInf = std::numeric_limits<double>::infinity();
229 const GraphType* const graph_;
230 const ArcLengths* const arc_lengths_;
231 absl::Span<const NodeIndex> const topological_order_;
232 const int path_count_;
233
234 GraphType reverse_graph_;
235 // Maps reverse arc indices to indices in the original graph.
236 std::vector<ArcIndex> arc_indices_;
237
238 // Data about the last call of the `RunKShortestPathOnDag()` function. The
239 // first dimension is the index of the path (1st being the shortest). The
240 // second dimension are nodes.
241 std::vector<std::vector<double>> lengths_from_sources_;
242 std::vector<std::vector<ArcIndex>> incoming_shortest_paths_arc_;
243 std::vector<std::vector<int>> incoming_shortest_paths_index_;
244 std::vector<bool> is_source_;
245 std::vector<NodeIndex> reached_nodes_;
246};
247
248template <class GraphType, typename ArcLengths>
249absl::Status TopologicalOrderIsValid(
250 const GraphType& graph,
251 absl::Span<const typename GraphType::NodeIndex> topological_order);
252
253// -----------------------------------------------------------------------------
254// Implementations.
255// -----------------------------------------------------------------------------
256// TODO(b/332475804): If `ArcPathTo` and/or `NodePathTo` functions become
257// bottlenecks:
258// (1) have the class preallocate a buffer of size `num_nodes`
259// (2) assign into an index rather than with push_back
260// (3) return by absl::Span (or return a copy) with known size.
261template <typename GraphType>
262std::vector<typename GraphType::NodeIndex> NodePathImpliedBy(
263 absl::Span<const typename GraphType::ArcIndex> arc_path,
264 const GraphType& graph) {
265 CHECK(!arc_path.empty());
266 std::vector<typename GraphType::NodeIndex> node_path;
267 node_path.reserve(arc_path.size() + 1);
268 for (const typename GraphType::ArcIndex arc_index : arc_path) {
269 node_path.push_back(graph.Tail(arc_index));
270 }
271 node_path.push_back(graph.Head(arc_path.back()));
272 return node_path;
273}
274
275template <class GraphType>
276void CheckNodeIsValid(typename GraphType::NodeIndex node,
277 const GraphType& graph) {
278 CHECK_GE(node, typename GraphType::NodeIndex(0))
279 << "Node must be nonnegative. Input value: " << node;
280 CHECK_LT(node, graph.num_nodes())
281 << "Node must be a valid node. Input value: " << node
282 << ". Number of nodes in the input graph: " << graph.num_nodes();
283}
284
285template <class GraphType>
286absl::Status TopologicalOrderIsValid(
287 const GraphType& graph,
288 absl::Span<const typename GraphType::NodeIndex> topological_order) {
289 using NodeIndex = typename GraphType::NodeIndex;
290 using ArcIndex = typename GraphType::ArcIndex;
291 const NodeIndex num_nodes = graph.num_nodes();
292 if (topological_order.size() != static_cast<size_t>(num_nodes)) {
293 return absl::InvalidArgumentError(absl::StrFormat(
294 "topological_order.size() = %i, != graph.num_nodes() = %v",
295 topological_order.size(), num_nodes));
296 }
297 std::vector<NodeIndex> inverse_topology(static_cast<size_t>(num_nodes),
298 GraphType::kNilNode);
299 for (NodeIndex node(0); node < num_nodes; ++node) {
300 if (inverse_topology[static_cast<size_t>(
301 topological_order[static_cast<size_t>(node)])] !=
302 GraphType::kNilNode) {
303 return absl::InvalidArgumentError(
304 absl::StrFormat("node %v appears twice in topological order",
305 topological_order[static_cast<size_t>(node)]));
306 }
307 inverse_topology[static_cast<size_t>(
308 topological_order[static_cast<size_t>(node)])] = node;
309 }
310 for (NodeIndex tail(0); tail < num_nodes; ++tail) {
311 for (const ArcIndex arc : graph.OutgoingArcs(tail)) {
312 const NodeIndex head = graph.Head(arc);
313 if (inverse_topology[static_cast<size_t>(tail)] >=
314 inverse_topology[static_cast<size_t>(head)]) {
315 return absl::InvalidArgumentError(absl::StrFormat(
316 "arc (%v, %v) is inconsistent with topological order", tail, head));
317 }
318 }
319 }
320 return absl::OkStatus();
321}
322
323// -----------------------------------------------------------------------------
324// ShortestPathsOnDagWrapper implementation.
325// -----------------------------------------------------------------------------
326template <class GraphType, typename ArcLengths>
328 const GraphType* graph, const ArcLengths* arc_lengths,
329 absl::Span<const NodeIndex> topological_order)
330 : graph_(graph),
331 arc_lengths_(arc_lengths),
332 topological_order_(topological_order) {
333 const size_t num_nodes = static_cast<size_t>(graph_->num_nodes());
334 CHECK(graph_ != nullptr);
335 CHECK(arc_lengths_ != nullptr);
336 CHECK_GT(num_nodes, 0) << "The graph is empty: it has no nodes";
337#ifndef NDEBUG
338 CHECK_EQ(typename GraphType::ArcIndex(arc_lengths_->size()),
339 graph_->num_arcs());
340 for (const double arc_length : *arc_lengths_) {
341 CHECK(arc_length != -kInf && !std::isnan(arc_length))
342 << absl::StrFormat("length cannot be -inf nor NaN");
343 }
344 CHECK_OK(TopologicalOrderIsValid(*graph_, topological_order_))
345 << "Invalid topological order";
346#endif
347
348 // Memory allocation is done here and only once in order to avoid reallocation
349 // at each call of `RunShortestPathOnDag()` for better performance.
350 length_from_sources_.resize(num_nodes, kInf);
351 incoming_shortest_path_arc_.resize(num_nodes, GraphType::kNilArc);
352 reached_nodes_.reserve(num_nodes);
353}
354
355template <class GraphType, typename ArcLengths>
356void ShortestPathsOnDagWrapper<GraphType, ArcLengths>::RunShortestPathOnDag(
357 absl::Span<const NodeIndex> sources) {
358 // Caching the vector addresses allow to not fetch it on each access.
359 const absl::Span<double> length_from_sources =
360 absl::MakeSpan(length_from_sources_);
361 const absl::Span<const double> arc_lengths = *arc_lengths_;
362
363 // Avoid reassigning `incoming_shortest_path_arc_` at every call for better
364 // performance, so it only makes sense for nodes that are reachable from at
365 // least one source, the other ones will contain junk.
366 for (const NodeIndex node : reached_nodes_) {
367 length_from_sources[static_cast<size_t>(node)] = kInf;
368 }
369 DCHECK(std::all_of(length_from_sources.begin(), length_from_sources.end(),
370 [](double l) { return l == kInf; }));
371 reached_nodes_.clear();
372
373 for (const NodeIndex source : sources) {
374 CheckNodeIsValid(source, *graph_);
375 length_from_sources[static_cast<size_t>(source)] = 0.0;
376 }
377
378 for (const NodeIndex tail : topological_order_) {
379 const double length_to_tail =
380 length_from_sources[static_cast<size_t>(tail)];
381 // Stop exploring a node as soon as its length to all sources is +inf.
382 if (length_to_tail == kInf) {
383 continue;
384 }
385 reached_nodes_.push_back(tail);
386 for (const ArcIndex arc : graph_->OutgoingArcs(tail)) {
387 const NodeIndex head = graph_->Head(arc);
388 DCHECK(arc_lengths[static_cast<size_t>(arc)] != -kInf);
389 const double length_to_head =
390 arc_lengths[static_cast<size_t>(arc)] + length_to_tail;
391 if (length_to_head < length_from_sources[static_cast<size_t>(head)]) {
392 length_from_sources[static_cast<size_t>(head)] = length_to_head;
393 incoming_shortest_path_arc_[static_cast<size_t>(head)] = arc;
394 }
395 }
396 }
397}
398
399template <class GraphType, typename ArcLengths>
400bool ShortestPathsOnDagWrapper<GraphType, ArcLengths>::IsReachable(
401 NodeIndex node) const {
402 CheckNodeIsValid(node, *graph_);
403 return length_from_sources_[static_cast<size_t>(node)] < kInf;
404}
405
406template <class GraphType, typename ArcLengths>
407std::vector<typename GraphType::ArcIndex>
409 NodeIndex node) const {
410 CHECK(IsReachable(node));
411 std::vector<ArcIndex> arc_path;
412 NodeIndex current_node = node;
413 for (NodeIndex i(0); i < graph_->num_nodes(); ++i) {
414 ArcIndex current_arc =
415 incoming_shortest_path_arc_[static_cast<size_t>(current_node)];
416 if (current_arc == GraphType::kNilArc) {
417 break;
418 }
419 arc_path.push_back(current_arc);
420 current_node = graph_->Tail(current_arc);
421 }
422 absl::c_reverse(arc_path);
423 return arc_path;
424}
425
426template <class GraphType, typename ArcLengths>
427std::vector<typename GraphType::NodeIndex>
428ShortestPathsOnDagWrapper<GraphType, ArcLengths>::NodePathTo(
429 NodeIndex node) const {
430 const std::vector<typename GraphType::ArcIndex> arc_path = ArcPathTo(node);
431 if (arc_path.empty()) {
432 return {node};
433 }
434 return NodePathImpliedBy(ArcPathTo(node), *graph_);
435}
437// -----------------------------------------------------------------------------
438// KShortestPathsOnDagWrapper implementation.
439// -----------------------------------------------------------------------------
440template <class GraphType, typename ArcLengths>
442 const GraphType* graph, const ArcLengths* arc_lengths,
443 absl::Span<const NodeIndex> topological_order, const int path_count)
444 : graph_(graph),
445 arc_lengths_(arc_lengths),
446 topological_order_(topological_order),
447 path_count_(path_count) {
448 CHECK(graph_ != nullptr);
449 CHECK(arc_lengths_ != nullptr);
450 const size_t num_nodes = static_cast<size_t>(graph_->num_nodes());
451 CHECK_GT(num_nodes, 0) << "The graph is empty: it has no nodes";
452 CHECK_GT(path_count_, 0) << "path_count must be greater than 0";
453#ifndef NDEBUG
454 CHECK_EQ(typename GraphType::ArcIndex(arc_lengths_->size()),
455 graph_->num_arcs());
456 for (const double arc_length : *arc_lengths_) {
457 CHECK(arc_length != -kInf && !std::isnan(arc_length))
458 << absl::StrFormat("length cannot be -inf nor NaN");
459 }
460 CHECK_OK(TopologicalOrderIsValid(*graph_, topological_order_))
461 << "Invalid topological order";
462#endif
463
464 // TODO(b/332475713): Optimize if reverse graph is already provided in
465 // `GraphType`.
466 const ArcIndex num_arcs = graph_->num_arcs();
467 reverse_graph_ = GraphType(graph_->num_nodes(), num_arcs);
468 for (ArcIndex arc_index(0); arc_index < num_arcs; ++arc_index) {
469 reverse_graph_.AddArc(graph->Head(arc_index), graph->Tail(arc_index));
470 }
471 std::vector<ArcIndex> permutation;
472 reverse_graph_.Build(&permutation);
473 arc_indices_.resize(permutation.size());
474 if (!permutation.empty()) {
475 for (int i = 0; i < permutation.size(); ++i) {
476 arc_indices_[static_cast<size_t>(permutation[i])] = ArcIndex(i);
477 }
478 }
479
480 // Memory allocation is done here and only once in order to avoid reallocation
481 // at each call of `RunKShortestPathOnDag()` for better performance.
482 lengths_from_sources_.resize(path_count_);
483 incoming_shortest_paths_arc_.resize(path_count_);
484 incoming_shortest_paths_index_.resize(path_count_);
485 for (int k = 0; k < path_count_; ++k) {
486 lengths_from_sources_[k].resize(num_nodes, kInf);
487 incoming_shortest_paths_arc_[k].resize(num_nodes, GraphType::kNilArc);
488 incoming_shortest_paths_index_[k].resize(num_nodes, -1);
489 }
490 is_source_.resize(num_nodes, false);
491 reached_nodes_.reserve(num_nodes);
492}
493
494template <class GraphType, typename ArcLengths>
496 absl::Span<const NodeIndex> sources) {
497 // Caching the vector addresses allow to not fetch it on each access.
498 const absl::Span<const double> arc_lengths = *arc_lengths_;
499 const absl::Span<const ArcIndex> arc_indices = arc_indices_;
500
501 // Avoid reassigning `incoming_shortest_path_arc_` at every call for better
502 // performance, so it only makes sense for nodes that are reachable from at
503 // least one source, the other ones will contain junk.
504
505 for (const NodeIndex node : reached_nodes_) {
506 is_source_[static_cast<size_t>(node)] = false;
507 for (int k = 0; k < path_count_; ++k) {
508 lengths_from_sources_[k][static_cast<size_t>(node)] = kInf;
509 }
510 }
511 reached_nodes_.clear();
512#ifndef NDEBUG
513 for (int k = 0; k < path_count_; ++k) {
514 CHECK(std::all_of(lengths_from_sources_[k].begin(),
515 lengths_from_sources_[k].end(),
516 [](double l) { return l == kInf; }));
517 }
518#endif
519
520 for (const NodeIndex source : sources) {
521 CheckNodeIsValid(source, *graph_);
522 is_source_[static_cast<size_t>(source)] = true;
523 }
524
525 struct IncomingArcPath {
526 double path_length = 0.0;
527 ArcIndex arc_index = ArcIndex(0);
528 double arc_length = 0.0;
529 NodeIndex from = NodeIndex(0);
530 int path_index = 0;
531
532 bool operator<(const IncomingArcPath& other) const {
533 return std::tie(path_length, from) <
534 std::tie(other.path_length, other.from);
535 }
536 bool operator>(const IncomingArcPath& other) const { return other < *this; }
537 };
538 std::vector<IncomingArcPath> min_heap;
539 auto comp = std::greater<IncomingArcPath>();
540 for (const NodeIndex to : topological_order_) {
541 min_heap.clear();
542 if (is_source_[static_cast<size_t>(to)]) {
543 min_heap.push_back({.arc_index = GraphType::kNilArc});
544 }
545 for (const ArcIndex reverse_arc_index : reverse_graph_.OutgoingArcs(to)) {
546 const ArcIndex arc_index =
547 arc_indices.empty()
548 ? reverse_arc_index
549 : arc_indices[static_cast<size_t>(reverse_arc_index)];
550 const NodeIndex from = graph_->Tail(arc_index);
551 const double arc_length = arc_lengths[static_cast<size_t>(arc_index)];
552 DCHECK(arc_length != -kInf);
553 const double path_length =
554 lengths_from_sources_.front()[static_cast<size_t>(from)] + arc_length;
555 if (path_length == kInf) {
556 continue;
557 }
558 min_heap.push_back({.path_length = path_length,
559 .arc_index = arc_index,
560 .arc_length = arc_length,
561 .from = from});
562 std::push_heap(min_heap.begin(), min_heap.end(), comp);
563 }
564 if (min_heap.empty()) {
565 continue;
566 }
567 reached_nodes_.push_back(to);
568 for (int k = 0; k < path_count_; ++k) {
569 std::pop_heap(min_heap.begin(), min_heap.end(), comp);
570 IncomingArcPath& incoming_arc_path = min_heap.back();
571 lengths_from_sources_[k][static_cast<size_t>(to)] =
572 incoming_arc_path.path_length;
573 incoming_shortest_paths_arc_[k][static_cast<size_t>(to)] =
574 incoming_arc_path.arc_index;
575 incoming_shortest_paths_index_[k][static_cast<size_t>(to)] =
576 incoming_arc_path.path_index;
577 if (incoming_arc_path.arc_index != GraphType::kNilArc &&
578 incoming_arc_path.path_index < path_count_ - 1 &&
579 lengths_from_sources_[incoming_arc_path.path_index + 1]
580 [static_cast<size_t>(incoming_arc_path.from)] <
581 kInf) {
582 ++incoming_arc_path.path_index;
583 incoming_arc_path.path_length =
584 lengths_from_sources_[incoming_arc_path.path_index]
585 [static_cast<size_t>(incoming_arc_path.from)] +
586 incoming_arc_path.arc_length;
587 std::push_heap(min_heap.begin(), min_heap.end(), comp);
588 } else {
589 min_heap.pop_back();
590 if (min_heap.empty()) {
591 break;
592 }
593 }
594 }
595 }
596}
597
598template <class GraphType, typename ArcLengths>
600 NodeIndex node) const {
601 CheckNodeIsValid(node, *graph_);
602 return lengths_from_sources_.front()[static_cast<size_t>(node)] < kInf;
603}
604
605template <class GraphType, typename ArcLengths>
606std::vector<double>
608 NodeIndex node) const {
609 std::vector<double> lengths_to;
610 lengths_to.reserve(path_count_);
611 for (int k = 0; k < path_count_; ++k) {
612 const double length_to =
613 lengths_from_sources_[k][static_cast<size_t>(node)];
614 if (length_to == kInf) {
615 break;
616 }
617 lengths_to.push_back(length_to);
618 }
619 return lengths_to;
620}
621
622template <class GraphType, typename ArcLengths>
623std::vector<std::vector<typename GraphType::ArcIndex>>
625 NodeIndex node) const {
626 std::vector<std::vector<ArcIndex>> arc_paths;
627 arc_paths.reserve(path_count_);
628 for (int k = 0; k < path_count_; ++k) {
629 if (lengths_from_sources_[k][static_cast<size_t>(node)] == kInf) {
630 break;
631 }
632 std::vector<ArcIndex> arc_path;
633 int current_path_index = k;
634 NodeIndex current_node = node;
635 for (NodeIndex i(0); i < graph_->num_nodes(); ++i) {
636 ArcIndex current_arc =
637 incoming_shortest_paths_arc_[current_path_index]
638 [static_cast<size_t>(current_node)];
639 if (current_arc == GraphType::kNilArc) {
640 break;
641 }
642 arc_path.push_back(current_arc);
643 current_path_index =
644 incoming_shortest_paths_index_[current_path_index]
645 [static_cast<size_t>(current_node)];
646 current_node = graph_->Tail(current_arc);
647 }
648 absl::c_reverse(arc_path);
649 arc_paths.push_back(arc_path);
650 }
651 return arc_paths;
652}
653
654template <class GraphType, typename ArcLengths>
655std::vector<std::vector<typename GraphType::NodeIndex>>
657 NodeIndex node) const {
658 const std::vector<std::vector<ArcIndex>> arc_paths = ArcPathsTo(node);
659 std::vector<std::vector<NodeIndex>> node_paths(arc_paths.size());
660 for (int k = 0; k < arc_paths.size(); ++k) {
661 if (arc_paths[k].empty()) {
662 node_paths[k] = {node};
663 } else {
664 node_paths[k] = NodePathImpliedBy(arc_paths[k], *graph_);
665 }
667 return node_paths;
668}
669
670} // namespace operations_research
671#endif // OR_TOOLS_GRAPH_DAG_SHORTEST_PATH_H_
const std::vector< NodeIndex > & reached_nodes() const
std::vector< double > LengthsTo(NodeIndex node) const
const GraphType & graph() const
Accessors to the underlying graph and arc lengths.
KShortestPathsOnDagWrapper(const GraphType *graph, const ArcLengths *arc_lengths, absl::Span< const NodeIndex > topological_order, int path_count)
void RunKShortestPathOnDag(absl::Span< const NodeIndex > sources)
std::vector< std::vector< ArcIndex > > ArcPathsTo(NodeIndex node) const
std::vector< std::vector< NodeIndex > > NodePathsTo(NodeIndex node) const
std::vector< ArcIndex > ArcPathTo(NodeIndex node) const
ShortestPathsOnDagWrapper(const GraphType *graph, const ArcLengths *arc_lengths, absl::Span< const NodeIndex > topological_order)
std::vector< NodeIndex > NodePathTo(NodeIndex node) const
void RunShortestPathOnDag(absl::Span< const NodeIndex > sources)
const std::vector< NodeIndex > & reached_nodes() const
const GraphType & graph() const
Accessors to the underlying graph and arc lengths.
In SWIG mode, we don't want anything besides these top-level includes.
absl::Status TopologicalOrderIsValid(const GraphType &graph, absl::Span< const typename GraphType::NodeIndex > topological_order)
std::vector< PathWithLength > KShortestPathsOnDag(const int num_nodes, absl::Span< const ArcWithLength > arcs_with_length, const int source, const int destination, const int path_count)
BlossomGraph::NodeIndex NodeIndex
ClosedInterval::Iterator end(ClosedInterval interval)
void CheckNodeIsValid(typename GraphType::NodeIndex node, const GraphType &graph)
std::vector< typename GraphType::NodeIndex > NodePathImpliedBy(absl::Span< const typename GraphType::ArcIndex > arc_path, const GraphType &graph)
PathWithLength ShortestPathsOnDag(const int num_nodes, absl::Span< const ArcWithLength > arcs_with_length, const int source, const int destination)
ClosedInterval::Iterator begin(ClosedInterval interval)
trees with all degrees equal to