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 
24 namespace 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.
std::vector< NodeIndex > GetIndexToNodeMap() const
absl::StrongVector< NodeIndex, int64 > GetNodeToIndexMap() const
RoutingIndexManager(int num_nodes, int num_vehicles, const std::vector< std::pair< NodeIndex, NodeIndex > > &starts_ends)
std::vector< int64 > NodesToIndices(const std::vector< NodeIndex > &nodes) const
RoutingIndexManager(int num_nodes, int num_vehicles, NodeIndex depot)
Creates a NodeIndex to variable index mapping for a problem containing 'num_nodes',...
RoutingIndexManager(int num_nodes, int num_vehicles, const std::vector< NodeIndex > &starts, const std::vector< NodeIndex > &ends)
std::vector< NodeIndex > IndicesToNodes(const std::vector< int64 > &indices) const
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...