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"
19 #include "ortools/base/logging.h"
20 #include "ortools/base/map_util.h"
21 
22 namespace operations_research {
23 
25 
26 RoutingIndexManager::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 
32 RoutingIndexManager::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 
50 void 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 
135 std::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...
int index
Definition: pack.cc:508