C++ Reference

C++ Reference: Routing

routing_index_manager.h
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
14#ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_INDEX_MANAGER_H_
15#define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_INDEX_MANAGER_H_
16
17#include <tuple>
18#include <vector>
19
20#include "ortools/base/logging.h"
21#include "ortools/base/strong_vector.h"
23
24namespace operations_research {
25
49 public:
50 typedef RoutingNodeIndex NodeIndex;
51 static const int64 kUnassigned;
52
59 const std::vector<NodeIndex>& starts,
60 const std::vector<NodeIndex>& ends);
62 int num_nodes, int num_vehicles,
63 const std::vector<std::pair<NodeIndex, NodeIndex> >& starts_ends);
65
66 // Returns the number of nodes in the manager.
67 int num_nodes() const { return num_nodes_; }
68 // Returns the number of vehicles in the manager.
69 int num_vehicles() const { return num_vehicles_; }
70 // Returns the number of indices mapped to nodes.
71 int num_indices() const { return index_to_node_.size(); }
72 // Returns start and end indices of the given vehicle.
73 int64 GetStartIndex(int vehicle) const { return vehicle_to_start_[vehicle]; }
74 int64 GetEndIndex(int vehicle) const { return vehicle_to_end_[vehicle]; }
75 // Returns the index of a node. A node can correspond to multiple indices if
76 // it's a start or end node. As of 03/2020, kUnassigned will be returned for
77 // all end nodes. If a node appears more than once as a start node, the index
78 // of the first node in the list of start nodes is returned.
79 int64 NodeToIndex(NodeIndex node) const {
80 DCHECK_GE(node.value(), 0);
81 DCHECK_LT(node.value(), node_to_index_.size());
82 return node_to_index_[node];
83 }
84 // Same as NodeToIndex but for a given vector of nodes.
85 std::vector<int64> NodesToIndices(const std::vector<NodeIndex>& nodes) const;
86 // Returns the node corresponding to an index. A node may appear more than
87 // once if it is used as the start or the end node of multiple vehicles.
88 NodeIndex IndexToNode(int64 index) const {
89 DCHECK_GE(index, 0);
90 DCHECK_LT(index, index_to_node_.size());
91 return index_to_node_[index];
92 }
93 // Same as IndexToNode but for a given vector of indices.
94 std::vector<NodeIndex> IndicesToNodes(
95 const std::vector<int64>& indices) const;
96 // TODO(user) Add unit tests for NodesToIndices and IndicesToNodes.
97 // TODO(user): Remove when removal of NodeIndex from RoutingModel is
99 int num_unique_depots() const { return num_unique_depots_; }
100 std::vector<NodeIndex> GetIndexToNodeMap() const { return index_to_node_; }
101 absl::StrongVector<NodeIndex, int64> GetNodeToIndexMap() const {
102 return node_to_index_;
103 }
104
105 private:
106 void Initialize(
107 int num_nodes, int num_vehicles,
108 const std::vector<std::pair<NodeIndex, NodeIndex> >& starts_ends);
109
110 std::vector<NodeIndex> index_to_node_;
111 absl::StrongVector<NodeIndex, int64> node_to_index_;
112 std::vector<int64> vehicle_to_start_;
113 std::vector<int64> vehicle_to_end_;
114 int num_nodes_;
115 int num_vehicles_;
116 int num_unique_depots_;
117};
118
119} // namespace operations_research
120
121#endif // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_INDEX_MANAGER_H_
Manager for any NodeIndex <-> variable index conversion.
RoutingIndexManager(int num_nodes, int num_vehicles, const std::vector< std::pair< NodeIndex, NodeIndex > > &starts_ends)
RoutingIndexManager(int num_nodes, int num_vehicles, NodeIndex depot)
Creates a NodeIndex to variable index mapping for a problem containing 'num_nodes',...
absl::StrongVector< NodeIndex, int64 > GetNodeToIndexMap() const
std::vector< NodeIndex > IndicesToNodes(const std::vector< int64 > &indices) const
std::vector< NodeIndex > GetIndexToNodeMap() const
RoutingIndexManager(int num_nodes, int num_vehicles, const std::vector< NodeIndex > &starts, const std::vector< NodeIndex > &ends)
std::vector< int64 > NodesToIndices(const std::vector< NodeIndex > &nodes) const
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...