38 ArcFlowBuilder(
const std::vector<int>& bin_dimensions,
39 absl::Span<
const std::vector<int>> item_dimensions_by_type,
40 absl::Span<const int> demand_by_type);
47 int64_t NumDpStates()
const;
57 double NormalizedSize(absl::Span<const int> bin_dimensions)
const;
73 void ForwardCreationPass(DpState* dp_state);
76 void BackwardCompressionPass(
int state_index);
78 void ForwardCompressionPass(
const std::vector<int>& source_node);
81 bool CanFitNewItem(absl::Span<const int>
used_dimensions,
int item)
const;
87 int LookupOrCreateDpState(
int item,
int quantity,
90 const std::vector<int> bin_dimensions_;
91 std::vector<Item> items_;
93 typedef absl::flat_hash_map<std::vector<int>,
int> VectorIntIntMap;
99 std::vector<DpState*> dp_states_;
100 std::vector<std::vector<VectorIntIntMap>> dp_state_index_;
106 absl::flat_hash_map<std::vector<int>,
int> node_indices_;
107 std::vector<std::vector<int>> nodes_;
109 std::set<ArcFlowGraph::Arc> arcs_;
112double ArcFlowBuilder::Item::NormalizedSize(
113 absl::Span<const int> bin_dimensions)
const {
115 for (
int i = 0;
i < bin_dimensions.size(); ++
i) {
121int64_t ArcFlowBuilder::NumDpStates()
const {
123 for (
const auto& it1 : dp_state_index_) {
124 for (
const auto& it2 : it1) {
131ArcFlowBuilder::ArcFlowBuilder(
132 const std::vector<int>& bin_dimensions,
133 absl::Span<
const std::vector<int>> item_dimensions_by_type,
134 absl::Span<const int> demand_by_type)
135 : bin_dimensions_(bin_dimensions) {
137 for (
int i = 0;
i < bin_dimensions.size(); ++
i) {
138 CHECK_GT(bin_dimensions[i], 0);
141 const int num_items = item_dimensions_by_type.size();
142 items_.resize(num_items);
143 for (
int i = 0;
i < num_items; ++
i) {
144 items_[
i].dimensions = item_dimensions_by_type[
i];
145 items_[
i].demand = demand_by_type[
i];
146 items_[
i].original_index =
i;
148 std::sort(items_.begin(), items_.end(), [&](
const Item&
a,
const Item&
b) {
149 return a.NormalizedSize(bin_dimensions_) >
150 b.NormalizedSize(bin_dimensions_);
154bool ArcFlowBuilder::CanFitNewItem(absl::Span<const int>
used_dimensions,
156 for (
int d = 0; d < bin_dimensions_.size(); ++d) {
164std::vector<int> ArcFlowBuilder::AddItem(
168 for (
int d = 0; d < bin_dimensions_.size(); ++d) {
169 result[d] += items_[item].dimensions[d];
174int ArcFlowBuilder::GetOrCreateNode(
const std::vector<int>&
used_dimensions) {
176 if (it != node_indices_.end()) {
179 const int index = node_indices_.size();
185ArcFlowGraph ArcFlowBuilder::BuildVectorBinPackingGraph() {
187 dp_state_index_.resize(items_.size());
188 for (
int i = 0;
i < items_.size(); ++
i) {
189 dp_state_index_[
i].resize(items_[i].
demand + 1);
194 std::vector<int> zero(bin_dimensions_.size(), 0);
195 dp_states_.push_back(
new DpState({0, 0, zero, -1, -1}));
196 for (
int i = 0;
i < dp_states_.size(); ++
i) {
197 ForwardCreationPass(dp_states_[i]);
203 const int64_t num_dp_states = NumDpStates();
204 dp_state_index_.clear();
207 const int num_states = dp_states_.size();
208 std::vector<std::pair<int, int>> flat_deps;
209 for (
int i = 0;
i < dp_states_.size(); ++
i) {
210 if (dp_states_[i]->
up_child != -1) {
211 flat_deps.push_back(std::make_pair(dp_states_[i]->
up_child, i));
214 flat_deps.push_back(std::make_pair(dp_states_[i]->
right_child, i));
217 const std::vector<int> sorted_work =
219 for (
const int w : sorted_work) {
220 BackwardCompressionPass(
w);
224 const std::vector<int> source_node = dp_states_[0]->used_dimensions;
227 ForwardCompressionPass(source_node);
231 const int sink_node_index = nodes_.size() - 1;
232 for (
int node = 1; node < sink_node_index; ++node) {
233 arcs_.insert({node, sink_node_index, -1});
237 result.arcs.assign(arcs_.begin(), arcs_.end());
238 result.nodes.assign(nodes_.begin(), nodes_.end());
239 result.num_dp_states = num_dp_states;
243int ArcFlowBuilder::LookupOrCreateDpState(
245 VectorIntIntMap& map = dp_state_index_[item][quantity];
248 if (
index == dp_states_.size()) {
249 dp_states_.push_back(
255void ArcFlowBuilder::ForwardCreationPass(DpState* dp_state) {
256 const int item = dp_state->cur_item_index;
257 const int quantity = dp_state->cur_item_quantity;
261 if (item < items_.size() - 1) {
262 dp_state->up_child = LookupOrCreateDpState(item + 1, 0,
used_dimensions);
264 dp_state->up_child = -1;
270 dp_state->right_child = LookupOrCreateDpState(item, quantity + 1, added);
272 dp_state->right_child = -1;
276void ArcFlowBuilder::BackwardCompressionPass(
int state_index) {
278 std::vector<int>& result = dp_states_[state_index]->used_dimensions;
281 const int up_index = dp_states_[state_index]->up_child;
282 const std::vector<int>& result_up =
283 up_index == -1 ? bin_dimensions_ : dp_states_[up_index]->used_dimensions;
287 const int right_index = dp_states_[state_index]->right_child;
288 if (right_index == -1)
return;
289 const std::vector<int>& result_right =
290 dp_states_[right_index]->used_dimensions;
291 const Item& item = items_[dp_states_[state_index]->cur_item_index];
292 for (
int d = 0; d < bin_dimensions_.size(); ++d) {
293 result[d] = std::min(result[d], result_right[d] - item.dimensions[d]);
297 const int node = GetOrCreateNode(result);
298 const int right_node = GetOrCreateNode(result_right);
299 DCHECK_NE(node, right_node);
300 arcs_.insert({node, right_node, item.original_index});
302 if (result != result_up) {
303 const int up_node = GetOrCreateNode(result_up);
304 arcs_.insert({node, up_node, -1});
312void ArcFlowBuilder::ForwardCompressionPass(
313 const std::vector<int>& source_node) {
314 const int num_nodes = node_indices_.size();
315 const int num_dims = bin_dimensions_.size();
316 std::set<ArcFlowGraph::Arc> new_arcs;
317 std::vector<std::vector<int>> new_nodes;
318 VectorIntIntMap new_node_indices;
319 std::vector<int> node_remap(num_nodes, -1);
321 std::vector<int> reverse_item_index_map(items_.size(), -1);
322 for (
int i = 0;
i < items_.size(); ++
i) {
323 reverse_item_index_map[items_[
i].original_index] =
i;
326 std::vector<std::pair<int, int>> forward_deps;
327 std::vector<std::vector<ArcFlowGraph::Arc>> incoming_arcs(num_nodes);
328 for (
const ArcFlowGraph::Arc&
arc : arcs_) {
329 forward_deps.push_back(std::make_pair(
arc.source,
arc.destination));
330 incoming_arcs[
arc.destination].push_back(
arc);
333 const std::vector<int> sorted_work =
336 const int old_source_node = GetOrCreateNode(source_node);
337 const int old_sink_node = GetOrCreateNode(bin_dimensions_);
338 CHECK_EQ(sorted_work.front(), old_source_node);
339 CHECK_EQ(sorted_work.back(), old_sink_node);
343 for (
const int w : sorted_work) {
344 std::vector<int> new_used(num_dims, 0);
345 if (
w == sorted_work.back()) {
346 new_used = bin_dimensions_;
348 for (
const ArcFlowGraph::Arc&
arc : incoming_arcs[
w]) {
350 arc.item_index == -1 ? -1 : reverse_item_index_map[
arc.item_index];
351 const int prev_node = node_remap[
arc.source];
352 const std::vector<int>& prev = new_nodes[prev_node];
353 DCHECK_NE(prev_node, -1);
354 for (
int d = 0; d < num_dims; ++d) {
357 std::max(new_used[d], prev[d] + items_[item].
dimensions[d]);
359 new_used[d] = std::max(new_used[d], prev[d]);
364 const auto& it = new_node_indices.find(new_used);
365 if (it != new_node_indices.end()) {
366 node_remap[
w] = it->second;
368 const int new_index = new_nodes.size();
369 new_nodes.push_back(new_used);
370 new_node_indices[new_used] = new_index;
371 node_remap[
w] = new_index;
375 for (
const ArcFlowGraph::Arc&
arc : arcs_) {
376 CHECK_NE(node_remap[
arc.source], -1);
377 CHECK_NE(node_remap[
arc.destination], -1);
379 if (
arc.item_index == -1 &&
380 node_remap[
arc.source] == node_remap[
arc.destination])
383 {node_remap[
arc.source], node_remap[
arc.destination],
arc.item_index});
385 VLOG(1) <<
"Reduced nodes from " << num_nodes <<
" to " << new_nodes.size();
386 VLOG(1) <<
"Reduced arcs from " << arcs_.size() <<
" to " << new_arcs.size();
389 CHECK_NE(node_remap[old_source_node], -1);
390 CHECK_EQ(0, node_remap[old_source_node]);
391 CHECK_NE(node_remap[old_sink_node], -1);
392 CHECK_EQ(nodes_.size() - 1, node_remap[old_sink_node]);
398 if (source != other.
source)
return source < other.
source;
404 const std::vector<int>& bin_dimensions,
405 absl::Span<
const std::vector<int>> item_dimensions_by_type,
406 absl::Span<const int> demand_by_type) {
407 ArcFlowBuilder afb(bin_dimensions, item_dimensions_by_type, demand_by_type);
408 return afb.BuildVectorBinPackingGraph();