OR-Tools  8.2
routing_index_manager.cc
Go to the documentation of this file.
1// Copyright 2010-2018 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 <memory>
17
18#include "absl/container/flat_hash_set.h"
21
22namespace operations_research {
23
25
26RoutingIndexManager::RoutingIndexManager(int num_nodes, int num_vehicles,
27 NodeIndex depot)
28 : RoutingIndexManager(num_nodes, num_vehicles,
29 std::vector<std::pair<NodeIndex, NodeIndex>>(
30 num_vehicles, {depot, depot})) {}
31
32RoutingIndexManager::RoutingIndexManager(int num_nodes, int num_vehicles,
33 const std::vector<NodeIndex>& starts,
34 const std::vector<NodeIndex>& ends) {
35 CHECK_EQ(starts.size(), num_vehicles);
36 CHECK_EQ(ends.size(), num_vehicles);
37 std::vector<std::pair<NodeIndex, NodeIndex>> starts_ends(num_vehicles);
38 for (int v = 0; v < num_vehicles; ++v) {
39 starts_ends[v] = {starts[v], ends[v]};
40 }
41 Initialize(num_nodes, num_vehicles, starts_ends);
42}
43
45 int num_nodes, int num_vehicles,
46 const std::vector<std::pair<NodeIndex, NodeIndex>>& starts_ends) {
47 Initialize(num_nodes, num_vehicles, starts_ends);
48}
49
50void RoutingIndexManager::Initialize(
51 int num_nodes, int num_vehicles,
52 const std::vector<std::pair<NodeIndex, NodeIndex>>& starts_ends) {
53 static const NodeIndex kZeroNode(0);
54
55 num_nodes_ = num_nodes;
56 num_vehicles_ = num_vehicles;
57 CHECK_EQ(num_vehicles_, starts_ends.size());
58 absl::flat_hash_set<NodeIndex> starts;
59 absl::flat_hash_set<NodeIndex> ends;
60 absl::flat_hash_set<NodeIndex> unique_depots;
61 for (const std::pair<NodeIndex, NodeIndex>& start_end : starts_ends) {
62 const NodeIndex start = start_end.first;
63 const NodeIndex end = start_end.second;
64 CHECK_GE(start, 0);
65 CHECK_GE(end, 0);
66 CHECK_LE(start, num_nodes_);
67 CHECK_LE(end, num_nodes_);
68 starts.insert(start);
69 ends.insert(end);
70 unique_depots.insert(start);
71 unique_depots.insert(end);
72 }
73 num_unique_depots_ = unique_depots.size();
74 const int size = num_nodes_ + num_vehicles_ - num_unique_depots_;
75
76 index_to_node_.resize(size + num_vehicles_);
77 node_to_index_.resize(num_nodes_, kUnassigned);
78 vehicle_to_start_.resize(num_vehicles_);
79 vehicle_to_end_.resize(num_vehicles_);
80 int64 index = 0;
81 for (NodeIndex i = kZeroNode; i < num_nodes_; ++i) {
82 if (gtl::ContainsKey(starts, i) || !gtl::ContainsKey(ends, i)) {
83 index_to_node_[index] = i;
84 node_to_index_[i] = index;
85 ++index;
86 }
87 }
88 absl::flat_hash_set<NodeIndex> seen_starts;
89 for (int i = 0; i < num_vehicles_; ++i) {
90 const NodeIndex start = starts_ends[i].first;
91 if (!gtl::ContainsKey(seen_starts, start)) {
92 seen_starts.insert(start);
93 const int64 start_index = node_to_index_[start];
94 vehicle_to_start_[i] = start_index;
95 CHECK_NE(kUnassigned, start_index);
96 } else {
97 vehicle_to_start_[i] = index;
98 index_to_node_[index] = start;
99 ++index;
100 }
101 }
102 for (int i = 0; i < num_vehicles_; ++i) {
103 NodeIndex end = starts_ends[i].second;
104 index_to_node_[index] = end;
105 vehicle_to_end_[i] = index;
106 CHECK_LE(size, index);
107 ++index;
108 }
109
110 // Logging model information.
111 VLOG(1) << "Number of nodes: " << num_nodes_;
112 VLOG(1) << "Number of vehicles: " << num_vehicles_;
113 for (int64 index = 0; index < index_to_node_.size(); ++index) {
114 VLOG(2) << "Variable index " << index << " -> Node index "
115 << index_to_node_[index];
116 }
117 for (NodeIndex node = kZeroNode; node < node_to_index_.size(); ++node) {
118 VLOG(2) << "Node index " << node << " -> Variable index "
119 << node_to_index_[node];
120 }
121}
122
124 const std::vector<NodeIndex>& nodes) const {
125 std::vector<int64> indices;
126 indices.reserve(nodes.size());
127 for (const NodeIndex node : nodes) {
128 const int64 index = NodeToIndex(node);
130 indices.push_back(index);
131 }
132 return indices;
133}
134
135std::vector<RoutingIndexManager::NodeIndex> RoutingIndexManager::IndicesToNodes(
136 const std::vector<int64>& indices) const {
137 std::vector<NodeIndex> nodes;
138 nodes.reserve(indices.size());
139 for (const int64 index : indices) {
140 nodes.push_back(IndexToNode(index));
141 }
142 return nodes;
143}
144
145} // namespace operations_research
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
#define VLOG(verboselevel)
Definition: base/logging.h:978
void resize(size_type new_size)
size_type size() const
Manager for any NodeIndex <-> variable index conversion.
RoutingIndexManager(int num_nodes, int num_vehicles, NodeIndex depot)
Creates a NodeIndex to variable index mapping for a problem containing 'num_nodes',...
std::vector< int64 > NodesToIndices(const std::vector< NodeIndex > &nodes) const
std::vector< NodeIndex > IndicesToNodes(const std::vector< int64 > &indices) const
int64_t int64
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
STL namespace.
int index
Definition: pack.cc:508