From cb93a79f7c422fcaa6f52cc361fff9e277fca04d Mon Sep 17 00:00:00 2001
From: Jaron Kent-Dobias <jaron@kent-dobias.com>
Date: Fri, 30 Sep 2022 11:19:12 +0200
Subject: Save a lot of time by using the built-in update method.

---
 rbmp.cpp | 40 +++++++++++++++++++++-------------------
 1 file changed, 21 insertions(+), 19 deletions(-)

diff --git a/rbmp.cpp b/rbmp.cpp
index ddd76cb..84ed351 100644
--- a/rbmp.cpp
+++ b/rbmp.cpp
@@ -83,6 +83,10 @@ public:
   }
 };
 
+bool edgeMatched(PerfectMatching& pm, const Edge& e) {
+  return e.halfedges[0].getTail().index == pm.GetMatch(e.halfedges[0].getHead().index);
+}
+
 int main(int argc, char* argv[]) {
   unsigned n = 100;
 
@@ -110,22 +114,23 @@ int main(int argc, char* argv[]) {
   pm.options.verbose = false;
   pm.Solve();
 
-  std::reference_wrapper<Edge> eFlip = r.pick(G.edges);
+  std::vector<bool> matching(G.edges.size());
 
-  while (pm.GetMatch(eFlip.get().halfedges[0].getTail().index) != eFlip.get().halfedges[0].getHead().index) {
-    eFlip = r.pick(G.edges);
+  for (unsigned i = 0; i < G.edges.size(); i++) {
+    matching[i] = edgeMatched(pm, G.edges[i]);
   }
 
-  eFlip.get().weight = 1e10;
-
-  PerfectMatching pm2(G.vertices.size(), G.edges.size());
+  unsigned eFlip = r.variate<unsigned, std::uniform_int_distribution>(0, G.edges.size() - 1);
 
-  for (const Edge& e : G.edges) {
-    pm2.AddEdge(e.halfedges[0].getHead().index, e.halfedges[0].getTail().index, e.weight);
+  while (!matching[eFlip]) {
+    eFlip = r.variate<unsigned, std::uniform_int_distribution>(0, G.edges.size() - 1);
   }
 
-  pm2.options.verbose = false;
-  pm2.Solve();
+  pm.StartUpdate();
+  pm.UpdateCost(eFlip, 1e10);
+  pm.FinishUpdate();
+
+  pm.Solve();
 
   std::cout << n << std::endl;
 
@@ -140,17 +145,14 @@ int main(int argc, char* argv[]) {
   }
 
   unsigned m = 0;
-  for (unsigned i = 0; i < G.vertices.size() / 2; i++) {
-    unsigned j1 = pm.GetMatch(i);
-    unsigned j2 = pm2.GetMatch(i);
-
-    if (j1 != j2) {
+  for (unsigned i = 0; i < G.edges.size(); i++) {
+    if (matching[i] && !edgeMatched(pm, G.edges[i])) {
       m++;
       std::cout
-        << G.vertices[i].coordinate[0] << " "
-        << G.vertices[i].coordinate[1] << " "
-        << G.vertices[j2].coordinate[0] << " "
-        << G.vertices[j2].coordinate[1] << std::endl;
+        << G.edges[i].halfedges[0].getTail().coordinate[0] << " "
+        << G.edges[i].halfedges[0].getHead().coordinate[1] << " "
+        << G.edges[i].halfedges[1].getTail().coordinate[0] << " "
+        << G.edges[i].halfedges[1].getHead().coordinate[1] << std::endl;
     }
   }
 
-- 
cgit v1.2.3-70-g09d2