14#ifndef OR_TOOLS_GRAPH_BOUNDED_DIJKSTRA_H_
15#define OR_TOOLS_GRAPH_BOUNDED_DIJKSTRA_H_
25#include "absl/algorithm/container.h"
26#include "absl/base/attributes.h"
27#include "absl/log/check.h"
28#include "absl/types/span.h"
61template <
typename NodeIndex,
typename DistanceType>
64 absl::Span<const NodeIndex> heads, absl::Span<const DistanceType> lengths,
65 DistanceType limit = std::numeric_limits<DistanceType>::max());
73template <
typename Tag,
typename Native,
typename Val
idator>
77template <
typename IndexType,
typename ValueType>
79 std::conditional_t<is_strong_int<IndexType>::value,
81 std::vector<ValueType>>;
83template <
class T,
typename ArcIndex>
87 const T&
operator()(ArcIndex index)
const {
return c_[index]; }
116template <
class GraphType,
class DistanceType,
117 class ArcLengthFunctor = internal::ElementGetter<
118 DistanceType,
typename GraphType::ArcIndex>>
126 template <
typename T>
128 template <
typename T>
143 ArcLengthFunctor arc_length_functor);
150 NodeIndex source_node, DistanceType distance_limit) {
161 DistanceType distance_limit);
171 const std::vector<std::pair<NodeIndex, DistanceType>>&
172 sources_with_distance_offsets,
173 DistanceType distance_limit);
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);
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);
248 ABSL_DEPRECATED(
"Use ArcPathTo() instead.")
280 const GraphType&
graph()
const {
return *graph_; }
283 return *arc_lengths_;
286 const DistanceType length = arc_length_functor_(arc);
287 DCHECK_GE(length, 0);
297 const GraphType*
const graph_;
298 ArcLengthFunctor arc_length_functor_;
306 std::vector<NodeIndex> reached_nodes_;
309 struct NodeDistance {
311 DistanceType distance;
313 bool operator<(
const NodeDistance& other)
const {
329 return std::tie(distance, node) < std::tie(other.distance, other.node);
331 bool operator>(
const NodeDistance& other)
const {
return other < *
this; }
333 std::vector<NodeDistance> queue_;
339 std::vector<bool> is_destination_;
348template <
class GraphType,
class DistanceType,
class ArcLengthFunctor>
355 CHECK(arc_lengths_ !=
nullptr);
362template <
class GraphType,
class DistanceType,
class ArcLengthFunctor>
365 ArcLengthFunctor arc_length_functor)
367 arc_length_functor_(
std::move(arc_length_functor)),
368 arc_lengths_(nullptr) {}
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_) {}
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);
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 {};
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;
414 if (is_destination_[
static_cast<size_t>(node)] &&
416 destinations_with_distance_offsets[node_to_destination_index_[node]]
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);
425 distance_limit -= min_destination_distance_offset;
426 if (num_destinations_to_reach > num_destinations) {
427 num_destinations_to_reach = num_destinations;
430 num_destinations_to_reach);
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 =
441 destinations_with_distance_offsets
442 [node_to_destination_index_[settled_node]]
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;
456 sources_with_distance_offsets, settled_node_callback, distance_limit);
459 for (
const auto& [node, _] : destinations_with_distance_offsets) {
460 is_destination_[
static_cast<size_t>(node)] =
false;
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);
470 return sorted_destinations;
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;
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) {
505 for (
const NodeIndex node : reached_nodes_) {
506 is_reached_[node] =
false;
508 reached_nodes_.clear();
509 DCHECK(!absl::c_linear_search(is_reached_,
true));
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);
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;
522 DCHECK_LT(node, graph_->num_nodes());
523 const DistanceType distance = sources_with_distance_offsets[i].second;
525 if (distance >= distance_limit)
continue;
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;
533 node_to_source_index_[node] = i;
534 distances_[node] = distance;
536 for (
const NodeIndex source : reached_nodes_) {
537 queue_.push_back({source, distances_[source]});
539 std::make_heap(queue_.begin(), queue_.end(), std::greater<NodeDistance>());
542 while (!queue_.empty()) {
543 const NodeDistance top = queue_.front();
544 std::pop_heap(queue_.begin(), queue_.end(), std::greater<NodeDistance>());
549 if (distances_[top.node] < top.distance)
continue;
551 if (settled_node_callback) {
556 if (top.distance < distance_limit) {
557 settled_node_callback(top.node, top.distance, &distance_limit);
561 if (top.distance >= distance_limit) {
566 DCHECK_LT(top.distance, distance_limit);
570 const DistanceType limit = distance_limit - top.distance;
571 for (
const typename GraphType::ArcIndex arc :
572 graph_->OutgoingArcs(top.node)) {
579 if (arc_length >= limit)
continue;
580 const DistanceType candidate_distance = top.distance + arc_length;
582 const NodeIndex head = graph_->Head(arc);
583 if (is_reached_[head]) {
584 if (candidate_distance >= distances_[head])
continue;
586 is_reached_[head] =
true;
587 reached_nodes_.push_back(head);
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>());
598 return reached_nodes_;
601template <
class GraphType,
class DistanceType,
class ArcLengthFunctor>
602std::vector<typename GraphType::ArcIndex>
605 std::vector<typename GraphType::ArcIndex> output;
606 int loop_detector = 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];
615 std::reverse(output.begin(), output.end());
619template <
class GraphType,
class DistanceType,
class ArcLengthFunctor>
620std::vector<typename GraphType::NodeIndex>
623 std::vector<NodeIndex> output;
624 int loop_detector = 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];
633 std::reverse(output.begin(), output.end());
637template <
class GraphType,
class DistanceType,
class ArcLengthFunctor>
638typename GraphType::NodeIndex BoundedDijkstraWrapper<
639 GraphType, DistanceType,
640 ArcLengthFunctor>::SourceOfShortestPathToNode(
NodeIndex node)
const {
642 while (parents_[parent] != parent) parent = parents_[parent];
646template <
class GraphType,
class DistanceType,
class ArcLengthFunctor>
648 ArcLengthFunctor>::GetSourceIndex(
NodeIndex node)
651 DCHECK_LT(node,
NodeIndex(node_to_source_index_.size()));
652 return node_to_source_index_[node];
655template <
class GraphType,
class DistanceType,
class ArcLengthFunctor>
659 DCHECK_LT(node,
NodeIndex(node_to_destination_index_.size()));
660 return node_to_destination_index_[node];
667template <
typename NodeIndex,
typename DistanceType>
670 absl::Span<const NodeIndex> heads, absl::Span<const DistanceType> lengths,
671 DistanceType limit) {
678 CHECK_GE(destination, 0);
679 NodeIndex num_nodes = std::max(source + 1, destination + 1);
682 num_nodes = std::max(tail + 1, num_nodes);
686 num_nodes = std::max(head + 1, num_nodes);
690 const ArcIndex num_arcs = tails.size();
691 CHECK_EQ(num_arcs, heads.size());
692 CHECK_EQ(num_arcs, lengths.size());
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) {
701 CHECK_GE(lengths[a], 0);
702 graph.AddArc(tails[a], heads[a]);
704 std::vector<int> permutation;
705 graph.Build(&permutation);
711 &graph, &arc_lengths);
712 if (!wrapper.OneToOneShortestPath(source, destination, limit)) {
718 return {wrapper.distances()[destination], wrapper.NodePathTo(destination)};
const ByArc< DistanceType > & arc_lengths() const
GraphType::ArcIndex ArcIndex
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.
int GetDestinationIndex(NodeIndex node) const
NodeIndex SourceOfShortestPathToNode(NodeIndex node) const
GraphType::NodeIndex NodeIndex
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
DistanceType distance_type
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
int GetSourceIndex(NodeIndex node) 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())
void Permute(const IntVector &permutation, Array *array_to_permute)
trees with all degrees equal to