1

2

3

4

5

6

7

8

9

10

11

12

13

15

16#include <cstdint>

17#include <utility>

18#include <vector>

19

20#include "absl/container/flat_hash_set.h"

21#include "absl/log/check.h"

22#include "absl/types/span.h"

24

26

28

34

46

52

53void RoutingIndexManager::Initialize(

54 int num_nodes, int num_vehicles,

55 const std::vector<std::pair<NodeIndex, NodeIndex>>& starts_ends) {

56 static const NodeIndex kZeroNode(0);

57

60 CHECK_EQ(num_vehicles_, starts_ends.size());

61 absl::flat_hash_set<NodeIndex> starts;

62 absl::flat_hash_set<NodeIndex> ends;

63 absl::flat_hash_set<NodeIndex> unique_depots;

64 for (const std::pair<NodeIndex, NodeIndex>& start_end : starts_ends) {

65 const NodeIndex start = start_end.first;

67 CHECK_GE(start, 0);

68 CHECK_GE(end, 0);

69 CHECK_LE(start, num_nodes_);

70 CHECK_LE(end, num_nodes_);

71 starts.insert(start);

72 ends.insert(end);

73 unique_depots.insert(start);

74 unique_depots.insert(end);

75 }

76 num_unique_depots_ = unique_depots.size();

77 const int size = num_nodes_ + num_vehicles_ - num_unique_depots_;

78

79 index_to_node_.resize(size + num_vehicles_);

81 vehicle_to_start_.resize(num_vehicles_);

82 vehicle_to_end_.resize(num_vehicles_);

83 int64_t index = 0;

84 for (NodeIndex i = kZeroNode; i < num_nodes_; ++i) {

85 if (starts.contains(i) || !ends.contains(i)) {

86 index_to_node_[index] = i;

87 node_to_index_[i] = index;

88 ++index;

89 }

90 }

91 absl::flat_hash_set<NodeIndex> seen_starts;

92 for (int i = 0; i < num_vehicles_; ++i) {

93 const NodeIndex start = starts_ends[i].first;

94 if (!seen_starts.contains(start)) {

95 seen_starts.insert(start);

96 const int64_t start_index = node_to_index_[start];

97 vehicle_to_start_[i] = start_index;

99 } else {

100 vehicle_to_start_[i] = index;

101 index_to_node_[index] = start;

102 ++index;

103 }

104 }

105 for (int i = 0; i < num_vehicles_; ++i) {

107 index_to_node_[index] = end;

108 vehicle_to_end_[i] = index;

109 CHECK_LE(size, index);

110 ++index;

111 }

112

113

114 VLOG(1) << "Number of nodes: " << num_nodes_;

115 VLOG(1) << "Number of vehicles: " << num_vehicles_;

116 for (int64_t index = 0; index < index_to_node_.size(); ++index) {

117 VLOG(2) << "Variable index " << index << " -> Node index "

118 << index_to_node_[index];

119 }

120 for (NodeIndex node = kZeroNode; node < node_to_index_.size(); ++node) {

121 VLOG(2) << "Node index " << node << " -> Variable index "

122 << node_to_index_[node];

123 }

124}

125

137

147

148}