14#ifndef OR_TOOLS_GRAPH_DAG_SHORTEST_PATH_H_
15#define OR_TOOLS_GRAPH_DAG_SHORTEST_PATH_H_
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"
69 int num_nodes, absl::Span<const ArcWithLength> arcs_with_length,
int source,
77 int num_nodes, absl::Span<const ArcWithLength> arcs_with_length,
int source,
78 int destination,
int path_count);
88template <
class GraphType,
typename ArcLengthContainer = std::vector<
double>>
91 using NodeIndex =
typename GraphType::NodeIndex;
92 using ArcIndex =
typename GraphType::ArcIndex;
118 absl::Span<const NodeIndex> topological_order);
127 const std::vector<NodeIndex>&
reached_nodes()
const {
return reached_nodes_; }
131 return length_from_sources_[
static_cast<size_t>(node)];
133 std::vector<double>
LengthTo()
const {
return length_from_sources_; }
144 const GraphType&
graph()
const {
return *graph_; }
148 static constexpr double kInf = std::numeric_limits<double>::infinity();
149 const GraphType*
const graph_;
151 absl::Span<const NodeIndex>
const topological_order_;
154 std::vector<double> length_from_sources_;
155 std::vector<ArcIndex> incoming_shortest_path_arc_;
156 std::vector<NodeIndex> reached_nodes_;
166template <
class GraphType,
typename ArcLengthContainer = std::vector<
double>>
169 using NodeIndex =
typename GraphType::NodeIndex;
170 using ArcIndex =
typename GraphType::ArcIndex;
196 absl::Span<const NodeIndex> topological_order,
206 const std::vector<NodeIndex>&
reached_nodes()
const {
return reached_nodes_; }
222 const GraphType&
graph()
const {
return *graph_; }
224 int path_count()
const {
return path_count_; }
227 static constexpr double kInf = std::numeric_limits<double>::infinity();
229 const GraphType*
const graph_;
231 absl::Span<const NodeIndex>
const topological_order_;
232 const int path_count_;
234 GraphType reverse_graph_;
236 std::vector<ArcIndex> arc_indices_;
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_;
248template <
class GraphType,
typename ArcLengths>
250 const GraphType& graph,
251 absl::Span<const typename GraphType::NodeIndex> topological_order);
261template <
typename GraphType>
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));
271 node_path.push_back(graph.Head(arc_path.back()));
275template <
class GraphType>
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();
285template <
class GraphType>
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));
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)]));
307 inverse_topology[
static_cast<size_t>(
308 topological_order[
static_cast<size_t>(node)])] = node;
310 for (
NodeIndex tail(0); tail < num_nodes; ++tail) {
311 for (
const ArcIndex arc : graph.OutgoingArcs(tail)) {
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));
320 return absl::OkStatus();
326template <
class GraphType,
typename ArcLengths>
328 const GraphType* graph,
const ArcLengths* arc_lengths,
329 absl::Span<const NodeIndex> topological_order)
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";
338 CHECK_EQ(
typename GraphType::ArcIndex(arc_lengths_->size()),
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");
345 <<
"Invalid topological order";
350 length_from_sources_.resize(num_nodes, kInf);
351 incoming_shortest_path_arc_.resize(num_nodes, GraphType::kNilArc);
352 reached_nodes_.reserve(num_nodes);
355template <
class GraphType,
typename ArcLengths>
356void ShortestPathsOnDagWrapper<GraphType, ArcLengths>::RunShortestPathOnDag(
357 absl::Span<const NodeIndex> sources) {
359 const absl::Span<double> length_from_sources =
360 absl::MakeSpan(length_from_sources_);
361 const absl::Span<const double> arc_lengths = *arc_lengths_;
366 for (
const NodeIndex node : reached_nodes_) {
367 length_from_sources[
static_cast<size_t>(node)] = kInf;
369 DCHECK(std::all_of(length_from_sources.begin(), length_from_sources.end(),
370 [](
double l) { return l == kInf; }));
371 reached_nodes_.clear();
375 length_from_sources[
static_cast<size_t>(source)] = 0.0;
378 for (
const NodeIndex tail : topological_order_) {
379 const double length_to_tail =
380 length_from_sources[
static_cast<size_t>(tail)];
382 if (length_to_tail == kInf) {
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;
399template <
class GraphType,
typename ArcLengths>
400bool ShortestPathsOnDagWrapper<GraphType, ArcLengths>::IsReachable(
401 NodeIndex node)
const {
403 return length_from_sources_[
static_cast<size_t>(node)] < kInf;
406template <
class GraphType,
typename ArcLengths>
407std::vector<typename GraphType::ArcIndex>
411 std::vector<ArcIndex> arc_path;
413 for (
NodeIndex i(0); i < graph_->num_nodes(); ++i) {
415 incoming_shortest_path_arc_[
static_cast<size_t>(current_node)];
416 if (current_arc == GraphType::kNilArc) {
419 arc_path.push_back(current_arc);
420 current_node = graph_->Tail(current_arc);
422 absl::c_reverse(arc_path);
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()) {
440template <
class GraphType,
typename ArcLengths>
443 absl::Span<const NodeIndex> topological_order,
const int path_count)
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";
454 CHECK_EQ(
typename GraphType::ArcIndex(arc_lengths_->size()),
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");
461 <<
"Invalid topological order";
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));
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);
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);
490 is_source_.resize(num_nodes,
false);
491 reached_nodes_.reserve(num_nodes);
494template <
class GraphType,
typename ArcLengths>
496 absl::Span<const NodeIndex> sources) {
498 const absl::Span<const double> arc_lengths = *arc_lengths_;
499 const absl::Span<const ArcIndex> arc_indices = arc_indices_;
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;
511 reached_nodes_.clear();
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; }));
522 is_source_[
static_cast<size_t>(source)] =
true;
525 struct IncomingArcPath {
526 double path_length = 0.0;
527 ArcIndex arc_index = ArcIndex(0);
528 double arc_length = 0.0;
532 bool operator<(
const IncomingArcPath& other)
const {
533 return std::tie(path_length, from) <
534 std::tie(other.path_length, other.from);
536 bool operator>(
const IncomingArcPath& other)
const {
return other < *
this; }
538 std::vector<IncomingArcPath> min_heap;
539 auto comp = std::greater<IncomingArcPath>();
542 if (is_source_[
static_cast<size_t>(
to)]) {
543 min_heap.push_back({.arc_index = GraphType::kNilArc});
545 for (
const ArcIndex reverse_arc_index : reverse_graph_.OutgoingArcs(
to)) {
546 const ArcIndex 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) {
558 min_heap.push_back({.path_length = path_length,
559 .arc_index = arc_index,
560 .arc_length = arc_length,
562 std::push_heap(min_heap.begin(), min_heap.end(), comp);
564 if (min_heap.empty()) {
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)] <
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);
590 if (min_heap.empty()) {
598template <
class GraphType,
typename ArcLengths>
602 return lengths_from_sources_.front()[
static_cast<size_t>(node)] < kInf;
605template <
class GraphType,
typename ArcLengths>
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) {
617 lengths_to.push_back(length_to);
622template <
class GraphType,
typename ArcLengths>
623std::vector<std::vector<typename GraphType::ArcIndex>>
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) {
632 std::vector<ArcIndex> arc_path;
633 int current_path_index = k;
635 for (
NodeIndex i(0); i < graph_->num_nodes(); ++i) {
637 incoming_shortest_paths_arc_[current_path_index]
638 [
static_cast<size_t>(current_node)];
639 if (current_arc == GraphType::kNilArc) {
642 arc_path.push_back(current_arc);
644 incoming_shortest_paths_index_[current_path_index]
645 [
static_cast<size_t>(current_node)];
646 current_node = graph_->Tail(current_arc);
648 absl::c_reverse(arc_path);
649 arc_paths.push_back(arc_path);
654template <
class GraphType,
typename ArcLengths>
655std::vector<std::vector<typename GraphType::NodeIndex>>
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};
const std::vector< NodeIndex > & reached_nodes() const
ArcLengthContainer ArcLengths
bool IsReachable(NodeIndex node) const
const ArcLengths & arc_lengths() const
std::vector< double > LengthsTo(NodeIndex node) const
typename GraphType::NodeIndex NodeIndex
const GraphType & graph() const
Accessors to the underlying graph and arc lengths.
typename GraphType::ArcIndex ArcIndex
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
typename GraphType::ArcIndex ArcIndex
bool IsReachable(NodeIndex node) const
std::vector< double > LengthTo() const
const GraphType & graph() const
Accessors to the underlying graph and arc lengths.
ArcLengthContainer ArcLengths
typename GraphType::NodeIndex NodeIndex
const ArcLengths & arc_lengths() const
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
std::vector< int > node_path
std::vector< int > arc_path