42 absl::Span<const ArcWithLengthAndResources> arcs_with_length_and_resources,
43 int source,
int destination,
const std::vector<double>& max_resources) {
46 using ArcIndex = GraphType::ArcIndex;
48 const int num_arcs = arcs_with_length_and_resources.size();
49 GraphType graph(num_nodes, num_arcs);
50 std::vector<double> arc_lengths;
51 arc_lengths.reserve(num_arcs);
52 std::vector<std::vector<double>> arc_resources(max_resources.size());
53 for (
int i = 0; i < max_resources.size(); ++i) {
54 arc_resources[i].reserve(num_arcs);
56 for (
const auto& arc : arcs_with_length_and_resources) {
57 graph.AddArc(arc.from, arc.to);
58 arc_lengths.push_back(arc.length);
59 for (
int i = 0; i < arc.resources.size(); ++i) {
60 arc_resources[i].push_back(arc.resources[i]);
64 std::vector<ArcIndex> permutation;
65 graph.Build(&permutation);
67 for (
int i = 0; i < max_resources.size(); ++i) {
71 std::vector<ArcIndex> inverse_permutation =
74 const absl::StatusOr<std::vector<NodeIndex>> topological_order =
76 CHECK_OK(topological_order) <<
"arcs_with_length form a cycle.";
78 std::vector<NodeIndex> sources = {source};
79 std::vector<NodeIndex> destinations = {destination};
81 constrained_shortest_path_on_dag(&graph, &arc_lengths, &arc_resources,
82 *topological_order, sources,
83 destinations, &max_resources);
88 ApplyMapping(inverse_permutation, path_with_length.
arc_path);
90 return {.length = path_with_length.
length,
91 .arc_path = std::move(path_with_length.
arc_path),
92 .node_path = std::move(path_with_length.
node_path)};