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();
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) {
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;
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_;