16 #include "absl/memory/memory.h"
22 graph_ = absl::make_unique<BlossomGraph>(num_nodes);
24 matches_.assign(num_nodes, -1);
28 CHECK_GE(
cost, 0) <<
"Not supported for now, just shift your costs.";
30 VLOG(1) <<
"Ignoring self-arc: " <<
tail <<
" <-> " <<
head
40 optimal_solution_found_ =
false;
53 int64 overflow_detection =
CapAdd(maximum_edge_cost_, maximum_edge_cost_);
55 return Status::INTEGER_OVERFLOW;
58 const int num_nodes = matches_.size();
59 if (!graph_->Initialize())
return Status::INFEASIBLE;
60 VLOG(2) << graph_->DebugString();
61 VLOG(1) <<
"num_unmatched: " << num_nodes - graph_->NumMatched()
62 <<
" dual_objective: " << graph_->DualObjective();
64 while (graph_->NumMatched() != num_nodes) {
65 graph_->PrimalUpdates();
67 graph_->DebugCheckNoPossiblePrimalUpdates();
70 VLOG(1) <<
"num_unmatched: " << num_nodes - graph_->NumMatched()
71 <<
" dual_objective: " << graph_->DualObjective();
72 if (graph_->NumMatched() == num_nodes)
break;
75 graph_->ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue();
76 overflow_detection =
CapAdd(overflow_detection, std::abs(
delta.value()));
78 return Status::INTEGER_OVERFLOW;
81 if (
delta == 0)
break;
82 graph_->UpdateAllTrees(
delta);
85 VLOG(1) <<
"End: " << graph_->NumMatched() <<
" / " << num_nodes;
86 graph_->DisplayStats();
87 if (graph_->NumMatched() < num_nodes) {
88 return Status::INFEASIBLE;
90 VLOG(2) << graph_->DebugString();
91 CHECK(graph_->DebugDualsAreFeasible());
95 graph_->ExpandAllBlossoms();
96 for (
int i = 0; i < num_nodes; ++i) {
100 optimal_solution_found_ =
true;
101 optimal_cost_ = graph_->DualObjective().value();
102 if (optimal_cost_ ==
kint64max)
return Status::COST_OVERFLOW;
103 return Status::OPTIMAL;
112 BlossomGraph::EdgeIndex(-1);
118 nodes_.reserve(num_nodes);
119 root_blossom_node_.
resize(num_nodes);
120 for (
NodeIndex n(0); n < num_nodes; ++n) {
121 root_blossom_node_[n] = n;
122 nodes_.push_back(
Node(n));
133 const EdgeIndex
index(edges_.size());
144 CHECK(!is_initialized_);
145 is_initialized_ =
true;
147 for (
NodeIndex n(0); n < nodes_.size(); ++n) {
148 if (graph_[n].empty())
return false;
155 for (
const EdgeIndex e : graph_[n]) {
156 min_cost =
std::min(min_cost, edges_[e].pseudo_slack);
159 nodes_[n].pseudo_dual = min_cost / 2;
167 for (EdgeIndex e(0); e < edges_.size(); ++e) {
168 Edge& mutable_edge = edges_[e];
170 nodes_[mutable_edge.
head].pseudo_dual;
174 for (
NodeIndex n(0); n < nodes_.size(); ++n) {
180 for (
const EdgeIndex e : graph_[n]) {
181 min_slack =
std::min(min_slack, edges_[e].pseudo_slack);
185 nodes_[n].pseudo_dual += min_slack;
186 for (
const EdgeIndex e : graph_[n]) {
187 edges_[e].pseudo_slack -= min_slack;
195 for (
const EdgeIndex e : graph_[n]) {
196 const Edge& edge = edges_[e];
199 nodes_[edge.
tail].type = 0;
200 nodes_[edge.
tail].match = edge.
head;
201 nodes_[edge.
head].type = 0;
202 nodes_[edge.
head].match = edge.
tail;
209 for (
NodeIndex n(0); n < nodes_.size(); ++n) {
211 unmatched_nodes_.push_back(n);
222 for (
NodeIndex n(0); n < nodes_.size(); ++n) {
224 nodes_[n].pseudo_dual *= 2;
225 AddToDualObjective(nodes_[n].pseudo_dual);
227 nodes_[n].dual = nodes_[n].pseudo_dual;
230 for (EdgeIndex e(0); e < edges_.size(); ++e) {
232 edges_[e].pseudo_slack *= 2;
234 edges_[e].slack = edges_[e].pseudo_slack;
240 if (!unmatched_nodes_.empty()) {
241 primal_update_edge_queue_.clear();
242 for (EdgeIndex e(0); e < edges_.size(); ++e) {
243 Edge& edge = edges_[e];
244 const bool tail_is_plus = nodes_[edge.
tail].IsPlus();
245 const bool head_is_plus = nodes_[edge.
head].IsPlus();
246 if (tail_is_plus && head_is_plus) {
247 plus_plus_pq_.Add(&edge);
248 if (edge.
pseudo_slack == 0) primal_update_edge_queue_.push_back(e);
249 }
else if (tail_is_plus || head_is_plus) {
250 plus_free_pq_.Add(&edge);
251 if (edge.
pseudo_slack == 0) primal_update_edge_queue_.push_back(e);
262 for (
NodeIndex n(0); n < nodes_.size(); ++n) {
263 const Node& node = nodes_[n];
270 CHECK(!unmatched_nodes_.empty());
271 const CostValue tree_delta = nodes_[unmatched_nodes_.front()].tree_dual_delta;
273 if (!plus_plus_pq_.IsEmpty()) {
274 DCHECK_EQ(plus_plus_pq_.Top()->pseudo_slack % 2, 0) <<
"Non integer bound!";
275 plus_plus_slack = plus_plus_pq_.Top()->pseudo_slack / 2 - tree_delta;
276 best_update =
std::min(best_update, plus_plus_slack);
279 if (!plus_free_pq_.IsEmpty()) {
280 plus_free_slack = plus_free_pq_.Top()->pseudo_slack - tree_delta;
281 best_update =
std::min(best_update, plus_free_slack);
292 primal_update_edge_queue_.clear();
293 if (plus_plus_slack == best_update) {
294 plus_plus_pq_.AllTop(&tmp_all_tops_);
295 for (
const Edge* pt : tmp_all_tops_) {
296 primal_update_edge_queue_.push_back(EdgeIndex(pt - &edges_.front()));
299 if (plus_free_slack == best_update) {
300 plus_free_pq_.AllTop(&tmp_all_tops_);
301 for (
const Edge* pt : tmp_all_tops_) {
302 primal_update_edge_queue_.push_back(EdgeIndex(pt - &edges_.front()));
314 for (
const NodeIndex n : unmatched_nodes_) {
316 AddToDualObjective(
delta);
317 nodes_[n].tree_dual_delta +=
delta;
321 for (
NodeIndex n(0); n < nodes_.size(); ++n) {
322 const Node& node = nodes_[n];
331 const Node& node = nodes_[n];
333 return node.
match != n;
337 const Node& node = nodes_[n];
348 for (EdgeIndex e(0); e < edges_.size(); ++e) {
349 const Edge& edge = edges_[e];
350 if (Head(edge) == Tail(edge))
continue;
352 CHECK(!nodes_[Tail(edge)].is_internal);
353 CHECK(!nodes_[Head(edge)].is_internal);
354 if (
Slack(edge) != 0)
continue;
360 if (!nodes_[
tail].IsPlus())
continue;
362 if (nodes_[
head].IsFree()) {
366 if (nodes_[
head].IsPlus()) {
367 if (nodes_[
tail].root == nodes_[
head].root) {
374 for (
const Node& node : nodes_) {
375 if (node.IsMinus() && node.IsBlossom() &&
Dual(node) == 0) {
387 possible_shrink_.clear();
390 while (!primal_update_edge_queue_.empty()) {
391 const EdgeIndex e = primal_update_edge_queue_.back();
392 primal_update_edge_queue_.pop_back();
398 const Edge& edge = edges_[e];
399 if (
Slack(edge) != 0)
continue;
404 if (!nodes_[
tail].IsPlus())
continue;
406 if (nodes_[
head].IsFree()) {
408 }
else if (nodes_[
head].IsPlus()) {
409 if (nodes_[
tail].root != nodes_[
head].root) {
412 possible_shrink_.push_back(e);
418 for (
const EdgeIndex e : possible_shrink_) {
419 const Edge& edge = edges_[e];
422 const Node& tail_node = nodes_[
tail];
423 const Node& head_node = nodes_[
head];
431 if (!primal_update_edge_queue_.empty())
continue;
439 for (
NodeIndex n(0); n < nodes_.size(); ++n) {
440 const Node& node = nodes_[n];
446 if (num_expands == 0)
break;
452 for (
const Edge& edge : edges_) {
453 if (
Slack(edge) < 0)
return false;
457 for (
const Node& node : nodes_) {
458 if (node.IsBlossom() &&
Dual(node) < 0)
return false;
464 if (Tail(edge) == Head(edge))
return false;
465 if (nodes_[Tail(edge)].IsInternal())
return false;
466 if (nodes_[Head(edge)].IsInternal())
return false;
467 return Slack(edge) == 0;
483 head_node.
root = root;
488 const CostValue tree_dual = nodes_[root].tree_dual_delta;
491 for (
const EdgeIndex e : graph_[subnode]) {
492 Edge& edge = edges_[e];
493 const NodeIndex other_end = OtherEnd(edge, subnode);
494 if (other_end ==
head)
continue;
496 if (plus_free_pq_.Contains(&edge)) plus_free_pq_.Remove(&edge);
500 Node& leaf_node = nodes_[leaf];
501 leaf_node.
root = root;
507 for (
const NodeIndex subnode : SubNodes(leaf)) {
508 for (
const EdgeIndex e : graph_[subnode]) {
509 Edge& edge = edges_[e];
510 const NodeIndex other_end = OtherEnd(edge, subnode);
511 if (other_end == leaf)
continue;
513 const Node& other_node = nodes_[other_end];
514 if (other_node.
IsPlus()) {
516 DCHECK(plus_free_pq_.Contains(&edge));
517 DCHECK(!plus_plus_pq_.Contains(&edge));
518 plus_free_pq_.Remove(&edge);
519 plus_plus_pq_.Add(&edge);
522 primal_update_edge_queue_.push_back(e);
524 }
else if (other_node.
IsFree()) {
526 DCHECK(!plus_free_pq_.Contains(&edge));
527 DCHECK(!plus_plus_pq_.Contains(&edge));
528 plus_free_pq_.Add(&edge);
531 primal_update_edge_queue_.push_back(e);
538 void BlossomGraph::AppendNodePathToRoot(
NodeIndex n,
539 std::vector<NodeIndex>* path)
const {
542 n = nodes_[n].parent;
543 if (n == path->back())
break;
550 const Edge& edge = edges_[e];
551 VLOG(2) <<
"Augment " << Tail(edge) <<
" -> " << Head(edge);
553 DCHECK(nodes_[Tail(edge)].IsPlus());
554 DCHECK(nodes_[Head(edge)].IsPlus());
556 const NodeIndex root_a = nodes_[Tail(edge)].root;
557 const NodeIndex root_b = nodes_[Head(edge)].root;
561 std::vector<NodeIndex> node_path;
562 AppendNodePathToRoot(Tail(edge), &node_path);
563 std::reverse(node_path.begin(), node_path.end());
564 AppendNodePathToRoot(Head(edge), &node_path);
567 const CostValue delta_a = nodes_[root_a].tree_dual_delta;
568 const CostValue delta_b = nodes_[root_b].tree_dual_delta;
569 nodes_[root_a].tree_dual_delta = 0;
570 nodes_[root_b].tree_dual_delta = 0;
583 for (
NodeIndex n(0); n < nodes_.size(); ++n) {
584 Node& node = nodes_[n];
587 if (root != root_a && root != root_b)
continue;
591 for (
const NodeIndex subnode : SubNodes(n)) {
592 for (
const EdgeIndex e : graph_[subnode]) {
593 Edge& edge = edges_[e];
594 const NodeIndex other_end = OtherEnd(edge, subnode);
595 if (other_end == n)
continue;
601 const Node& other_node = nodes_[other_end];
602 if (other_node.
root != root_a && other_node.
root != root_b &&
604 if (plus_plus_pq_.Contains(&edge)) plus_plus_pq_.Remove(&edge);
605 DCHECK(!plus_free_pq_.Contains(&edge));
606 plus_free_pq_.Add(&edge);
607 if (
Slack(edge) == 0) primal_update_edge_queue_.push_back(e);
609 if (plus_plus_pq_.Contains(&edge)) plus_plus_pq_.Remove(&edge);
610 if (plus_free_pq_.Contains(&edge)) plus_free_pq_.Remove(&edge);
621 for (
int i = 0; i < node_path.size(); i += 2) {
622 nodes_[node_path[i]].match = node_path[i + 1];
623 nodes_[node_path[i + 1]].match = node_path[i];
632 for (
const NodeIndex n : unmatched_nodes_) {
635 CHECK_EQ(unmatched_nodes_.size(), new_size + 2);
636 unmatched_nodes_.resize(new_size);
639 int BlossomGraph::GetDepth(
NodeIndex n)
const {
642 const NodeIndex parent = nodes_[n].parent;
643 if (parent == n)
break;
653 const Edge& edge = edges_[e];
655 DCHECK(nodes_[Tail(edge)].IsPlus());
656 DCHECK(nodes_[Head(edge)].IsPlus());
657 DCHECK_EQ(nodes_[Tail(edge)].root, nodes_[Head(edge)].root);
659 CHECK_NE(Tail(edge), Head(edge)) << e;
664 std::vector<NodeIndex> tail_path;
665 std::vector<NodeIndex> head_path;
669 int tail_depth = GetDepth(
tail);
670 int head_depth = GetDepth(
head);
671 if (tail_depth > head_depth) {
673 std::swap(tail_depth, head_depth);
677 while (head_depth > tail_depth) {
678 head_path.push_back(
head);
690 tail_path.push_back(
tail);
693 head_path.push_back(
head);
697 VLOG(2) <<
"LCA " << lca_index;
699 Node& lca = nodes_[lca_index];
703 std::vector<NodeIndex> blossom = {lca_index};
704 std::reverse(head_path.begin(), head_path.end());
705 blossom.insert(blossom.end(), head_path.begin(), head_path.end());
706 blossom.insert(blossom.end(), tail_path.begin(), tail_path.end());
709 const CostValue tree_dual = nodes_[lca.
root].tree_dual_delta;
713 Node& backup_node = nodes_[blossom[1]];
731 if (n != lca_index) {
732 nodes_[n].is_internal =
true;
738 Node& mutable_node = nodes_[n];
739 const bool was_minus = mutable_node.
IsMinus();
741 mutable_node.
IsMinus() ? tree_dual : -tree_dual;
742 if (n != lca_index) {
747 mutable_node.
type = 0;
749 for (
const NodeIndex subnode : SubNodes(n)) {
753 root_blossom_node_[subnode] = lca_index;
755 for (
const EdgeIndex e : graph_[subnode]) {
756 Edge& edge = edges_[e];
757 const NodeIndex other_end = OtherEnd(edge, subnode);
760 if (other_end == n)
continue;
764 if (other_end == lca_index) {
777 Node& mutable_other_node = nodes_[other_end];
779 DCHECK(!plus_free_pq_.Contains(&edge));
780 if (plus_plus_pq_.Contains(&edge)) plus_plus_pq_.Remove(&edge);
783 mutable_other_node.
IsMinus() ? tree_dual : -tree_dual;
788 if (mutable_other_node.
parent == n) {
789 mutable_other_node.
parent = lca_index;
799 DCHECK(!plus_plus_pq_.Contains(&edge));
800 DCHECK(!plus_free_pq_.Contains(&edge));
801 if (mutable_other_node.
IsPlus()) {
802 plus_plus_pq_.Add(&edge);
804 primal_update_edge_queue_.push_back(e);
806 }
else if (mutable_other_node.
IsFree()) {
807 plus_free_pq_.Add(&edge);
809 primal_update_edge_queue_.push_back(e);
823 lca.
blossom = std::move(blossom);
828 BlossomGraph::EdgeIndex BlossomGraph::FindTightExternalEdgeBetweenNodes(
834 for (
const EdgeIndex e : graph_[subnode]) {
835 const Edge& edge = edges_[e];
836 const NodeIndex other_end = OtherEnd(edge, subnode);
837 if (other_end ==
head &&
Slack(edge) == 0) {
847 VLOG(2) <<
"Expand " << to_expand;
849 Node& node_to_expand = nodes_[to_expand];
854 const EdgeIndex match_edge_index =
855 FindTightExternalEdgeBetweenNodes(to_expand, node_to_expand.
match);
856 const EdgeIndex parent_edge_index =
857 FindTightExternalEdgeBetweenNodes(to_expand, node_to_expand.
parent);
860 Node& backup_node = nodes_[node_to_expand.
blossom[1]];
865 std::vector<NodeIndex> blossom = std::move(node_to_expand.
blossom);
871 for (
const NodeIndex subnode : SubNodes(n)) {
872 root_blossom_node_[subnode] = n;
884 int blossom_path_start = -1;
885 int blossom_path_end = -1;
886 const NodeIndex start_node = OtherEndFromExternalNode(
887 edges_[parent_edge_index], node_to_expand.
parent);
889 OtherEndFromExternalNode(edges_[match_edge_index], node_to_expand.
match);
890 for (
int i = 0; i < blossom.size(); ++i) {
891 if (blossom[i] == start_node) blossom_path_start = i;
892 if (blossom[i] == end_node) blossom_path_end = i;
897 const std::vector<NodeIndex>& cycle = blossom;
898 std::vector<NodeIndex> path1;
899 std::vector<NodeIndex> path2;
901 const int end_offset =
902 (blossom_path_end + cycle.size() - blossom_path_start) % cycle.size();
903 for (
int offset = 0; offset <= cycle.size(); ++offset) {
905 cycle[(blossom_path_start + offset) % cycle.size()];
906 if (offset <= end_offset) path1.push_back(node);
907 if (offset >= end_offset) path2.push_back(node);
912 std::reverse(path2.begin(), path2.end());
915 if (path1.size() % 2 == 0) path1.swap(path2);
918 std::vector<NodeIndex>& path_in_tree = path1;
919 const std::vector<NodeIndex>& free_pairs = path2;
922 path2.erase(path2.begin());
927 << absl::StrJoin(path_in_tree,
", ", absl::StreamFormatter())
928 <<
"] === " << blossom_matched_node;
930 << absl::StrJoin(free_pairs,
", ", absl::StreamFormatter()) <<
"]";
936 path_in_tree.push_back(blossom_matched_node);
937 CHECK_EQ(path_in_tree.size() % 2, 0);
938 const CostValue tree_dual = nodes_[node_to_expand.
root].tree_dual_delta;
939 for (
int i = 0; i < path_in_tree.size(); ++i) {
941 const bool node_is_plus = i % 2;
947 DCHECK(node_to_expand.
parent != to_expand || n == to_expand);
948 nodes_[n].parent = node_to_expand.
parent;
950 nodes_[n].parent = path_in_tree[i - 1];
954 nodes_[n].root = node_to_expand.
root;
955 nodes_[n].type = node_is_plus ? 1 : -1;
956 nodes_[n].match = path_in_tree[node_is_plus ? i - 1 : i + 1];
959 if (i + 1 == path_in_tree.size())
continue;
964 const CostValue adjust = node_is_plus ? -tree_dual : tree_dual;
965 nodes_[n].pseudo_dual += adjust;
966 for (
const NodeIndex subnode : SubNodes(n)) {
967 for (
const EdgeIndex e : graph_[subnode]) {
968 Edge& edge = edges_[e];
969 const NodeIndex other_end = OtherEnd(edge, subnode);
970 if (other_end == n)
continue;
976 if (other_end != to_expand && !nodes_[other_end].is_internal) {
983 if (nodes_[other_end].type == 0)
continue;
988 const Node& other_node = nodes_[other_end];
989 DCHECK(!plus_plus_pq_.Contains(&edge));
990 DCHECK(!plus_free_pq_.Contains(&edge));
991 if (other_node.
IsPlus()) {
992 plus_plus_pq_.Add(&edge);
994 primal_update_edge_queue_.push_back(e);
996 }
else if (other_node.
IsFree()) {
997 plus_free_pq_.Add(&edge);
999 primal_update_edge_queue_.push_back(e);
1010 nodes_[n].parent = n;
1014 for (
const NodeIndex subnode : SubNodes(n)) {
1015 for (
const EdgeIndex e : graph_[subnode]) {
1016 Edge& edge = edges_[e];
1017 const NodeIndex other_end = OtherEnd(edge, subnode);
1018 if (other_end == n)
continue;
1022 if (other_end != to_expand && !nodes_[other_end].is_internal) {
1028 DCHECK(!plus_plus_pq_.Contains(&edge));
1029 DCHECK(!plus_free_pq_.Contains(&edge));
1030 if (nodes_[other_end].IsPlus()) {
1031 plus_free_pq_.Add(&edge);
1033 primal_update_edge_queue_.push_back(e);
1041 CHECK_EQ(free_pairs.size() % 2, 0);
1042 for (
int i = 0; i < free_pairs.size(); i += 2) {
1043 nodes_[free_pairs[i]].match = free_pairs[i + 1];
1044 nodes_[free_pairs[i + 1]].match = free_pairs[i];
1050 nodes_[n].is_internal =
false;
1056 std::vector<NodeIndex> queue;
1057 for (
NodeIndex n(0); n < nodes_.size(); ++n) {
1058 Node& node = nodes_[n];
1064 if (node.
IsBlossom()) queue.push_back(n);
1068 while (!queue.empty()) {
1069 const NodeIndex to_expand = queue.back();
1072 Node& node_to_expand = nodes_[to_expand];
1076 const EdgeIndex match_edge_index =
1077 FindTightExternalEdgeBetweenNodes(to_expand, node_to_expand.
match);
1080 Node& backup_node = nodes_[node_to_expand.
blossom[1]];
1086 std::vector<NodeIndex> blossom = std::move(node_to_expand.
blossom);
1092 for (
const NodeIndex subnode : SubNodes(n)) {
1093 root_blossom_node_[subnode] = n;
1098 int internal_matched_index = -1;
1099 const NodeIndex matched_node = OtherEndFromExternalNode(
1100 edges_[match_edge_index], node_to_expand.
match);
1101 const int size = blossom.size();
1102 for (
int i = 0; i < size; ++i) {
1103 if (blossom[i] == matched_node) {
1104 internal_matched_index = i;
1108 CHECK_NE(internal_matched_index, -1);
1112 std::vector<NodeIndex> free_pairs;
1113 for (
int i = (internal_matched_index + 1) % size;
1114 i != internal_matched_index; i = (i + 1) % size) {
1115 free_pairs.push_back(blossom[i]);
1119 for (
const NodeIndex to_clear : blossom) {
1120 nodes_[to_clear].type = 0;
1121 nodes_[to_clear].is_internal =
false;
1122 nodes_[to_clear].parent = to_clear;
1123 nodes_[to_clear].root = to_clear;
1128 const NodeIndex internal_matched_node = blossom[internal_matched_index];
1129 nodes_[internal_matched_node].match = external_matched_node;
1130 nodes_[external_matched_node].match = internal_matched_node;
1133 CHECK_EQ(free_pairs.size() % 2, 0);
1134 for (
int i = 0; i < free_pairs.size(); i += 2) {
1135 nodes_[free_pairs[i]].match = free_pairs[i + 1];
1136 nodes_[free_pairs[i + 1]].match = free_pairs[i];
1141 if (nodes_[n].IsBlossom()) queue.push_back(n);
1146 const std::vector<NodeIndex>& BlossomGraph::SubNodes(
NodeIndex n) {
1150 DCHECK(nodes_[n].saved_blossom.empty());
1155 for (
int i = 0; i < subnodes_.size(); ++i) {
1156 const Node& node = nodes_[subnodes_[i]];
1160 if (!node.blossom.empty()) {
1161 subnodes_.insert(subnodes_.end(), node.blossom.begin() + 1,
1162 node.blossom.end());
1169 if (!node.saved_blossom.empty()) {
1170 subnodes_.insert(subnodes_.end(), node.saved_blossom.begin() + 1,
1171 node.saved_blossom.end());
1178 const Node& node = nodes_[n];
1180 return absl::StrCat(
"[I] #", n.value());
1183 : node.
type == 1 ?
"[+]"
1184 : node.
type == -1 ?
"[-]"
1186 return absl::StrCat(
1187 type,
" #", n.value(),
" dual: ",
Dual(node).
value(),
1188 " parent: ", node.
parent.value(),
" match: ", node.
match.value(),
1189 " blossom: [", absl::StrJoin(node.
blossom,
", ", absl::StreamFormatter()),
1194 const Edge& edge = edges_[e];
1195 if (nodes_[Tail(edge)].is_internal || nodes_[Head(edge)].is_internal) {
1196 return absl::StrCat(Tail(edge).
value(),
"<->", Head(edge).
value(),
1199 return absl::StrCat(Tail(edge).
value(),
"<->", Head(edge).
value(),
1204 std::string result =
"Graph:\n";
1205 for (
NodeIndex n(0); n < nodes_.size(); ++n) {
1208 for (EdgeIndex e(0); e < edges_.size(); ++e) {
1216 nodes_[n].dual +=
delta;
1217 for (
const NodeIndex subnode : SubNodes(n)) {
1218 for (
const EdgeIndex e : graph_[subnode]) {
1219 Edge& edge = edges_[e];
1220 const NodeIndex other_end = OtherEnd(edge, subnode);
1221 if (other_end == n)
continue;
1222 edges_[e].slack -=
delta;
1229 const Node& tail_node = nodes_[Tail(edge)];
1230 const Node& head_node = nodes_[Head(edge)];
1232 if (Tail(edge) == Head(edge))
return slack;
1235 slack -= tail_node.
type * nodes_[tail_node.
root].tree_dual_delta +
1236 head_node.
type * nodes_[head_node.
root].tree_dual_delta;
1240 <<
" " << Tail(edge) <<
"<->" << Head(edge);
1258 return dual_objective_ / 2;
1267 VLOG(1) <<
"num_grows: " << num_grows_;
1268 VLOG(1) <<
"num_augments: " << num_augments_;
1269 VLOG(1) <<
"num_shrinks: " << num_shrinks_;
1270 VLOG(1) <<
"num_expands: " << num_expands_;
1271 VLOG(1) <<
"num_dual_updates: " << num_dual_updates_;
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define DCHECK_GE(val1, val2)
#define CHECK_NE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
void resize(size_type new_size)
void push_back(const value_type &x)
bool DebugDualsAreFeasible() const
ABSL_MUST_USE_RESULT bool Initialize()
CostValue DualObjective() const
void Grow(EdgeIndex e, NodeIndex tail, NodeIndex head)
CostValue ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue()
bool DebugEdgeIsTightAndExternal(const Edge &edge) const
static const CostValue kMaxCostValue
NodeIndex Match(NodeIndex n) const
void AddEdge(NodeIndex tail, NodeIndex head, CostValue cost)
bool NodeIsMatched(NodeIndex n) const
CostValue Slack(const Edge &edge) const
std::string NodeDebugString(NodeIndex n) const
std::string EdgeDebugString(EdgeIndex e) const
void DebugCheckNoPossiblePrimalUpdates()
std::string DebugString() const
void Augment(EdgeIndex e)
CostValue Dual(const Node &node) const
static const EdgeIndex kNoEdgeIndex
static const NodeIndex kNoNodeIndex
void Expand(NodeIndex to_expand)
void UpdateAllTrees(CostValue delta)
void DisplayStats() const
void DebugUpdateNodeDual(NodeIndex n, CostValue delta)
BlossomGraph(int num_nodes)
ABSL_MUST_USE_RESULT Status Solve()
void Reset(int num_nodes)
void AddEdgeWithCost(int tail, int head, int64 cost)
static const int64 kint64max
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapAdd(int64 x, int64 y)
NodeIndex OtherEnd(NodeIndex n) const
std::vector< NodeIndex > blossom
CostValue saved_pseudo_dual
std::vector< NodeIndex > saved_blossom