Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
dag_constrained_shortest_path.cc
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
15
16#include <utility>
17#include <vector>
18
19#include "absl/log/check.h"
20#include "absl/status/statusor.h"
21#include "absl/types/span.h"
23#include "ortools/graph/graph.h"
25
26namespace operations_research {
27
28namespace {
29
30void ApplyMapping(absl::Span<const int> mapping, std::vector<int>& values) {
31 if (!mapping.empty()) {
32 for (int i = 0; i < values.size(); ++i) {
33 values[i] = mapping[values[i]];
34 }
35 }
36}
37
38} // namespace
39
41 const int num_nodes,
42 absl::Span<const ArcWithLengthAndResources> arcs_with_length_and_resources,
43 int source, int destination, const std::vector<double>& max_resources) {
44 using GraphType = util::StaticGraph<>;
45 using NodeIndex = GraphType::NodeIndex;
46 using ArcIndex = GraphType::ArcIndex;
47
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);
55 }
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]);
61 }
62 }
63
64 std::vector<ArcIndex> permutation;
65 graph.Build(&permutation);
66 util::Permute(permutation, &arc_lengths);
67 for (int i = 0; i < max_resources.size(); ++i) {
68 util::Permute(permutation, &arc_resources[i]);
69 }
70
71 std::vector<ArcIndex> inverse_permutation =
73
74 const absl::StatusOr<std::vector<NodeIndex>> topological_order =
76 CHECK_OK(topological_order) << "arcs_with_length form a cycle.";
77
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);
84
85 GraphPathWithLength<GraphType> path_with_length =
86 constrained_shortest_path_on_dag.RunConstrainedShortestPathOnDag();
87
88 ApplyMapping(inverse_permutation, path_with_length.arc_path);
89
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)};
93}
94
95} // namespace operations_research
std::vector< T > GetInversePermutation(const std::vector< T > &permutation)
In SWIG mode, we don't want anything besides these top-level includes.
BlossomGraph::NodeIndex NodeIndex
PathWithLength ConstrainedShortestPathsOnDag(const int num_nodes, absl::Span< const ArcWithLengthAndResources > arcs_with_length_and_resources, int source, int destination, const std::vector< double > &max_resources)
absl::StatusOr< std::vector< typename util::GraphTraits< AdjacencyLists >::NodeIndex > > FastTopologicalSort(const AdjacencyLists &adj)
void Permute(const IntVector &permutation, Array *array_to_permute)
Definition graph.h:1101
std::vector< typename GraphType::ArcIndex > arc_path
std::vector< typename GraphType::NodeIndex > node_path