adapt Tutte matching to new Gauss, and remove some global variables

3 files changed, 25 insertions, 33 deletions

diff --git a/test/graph/blossom.cpp b/test/graph/blossom.cpp
index 714b029..0add7e1 100644
--- a/test/graph/blossom.cpp
+++ b/test/graph/blossom.cpp
@@ -1,6 +1,6 @@
 #include "../util.h"
 namespace tutte {
-void gauss(int n, ll mod);
+vector<int> gauss(vector<vector<ll>> &mat);
 #include <graph/matching.cpp>
 #include <math/shortModInv.cpp>
 #include <math/lgsFp.cpp>
@@ -15,20 +15,20 @@ void stress_test() {
 
 		GM blossom(n);
 		srand(Random::rng());
-		tutte::adj.assign(n, {});
+		vector<vector<int>> adj(n);
 
 		Graph<NoData> g(n);
 		g.erdosRenyi(m);
 		g.forEdges([&](int a, int b){
-			tutte::adj[a].push_back(b);
-			tutte::adj[b].push_back(a);
+			adj[a].push_back(b);
+			adj[b].push_back(a);
 
 			blossom.adj[a].push_back(b);
 			blossom.adj[b].push_back(a);
 		});
 
 		ll got = blossom.match();
-		ll expected = tutte::max_matching();
+		ll expected = tutte::max_matching(adj);
 
 		vector<bool> seen(n);
 		ll got2 = 0;
diff --git a/test/graph/matching.cpp b/test/graph/matching.cpp
index b8fbc6c..9e3ad85 100644
--- a/test/graph/matching.cpp
+++ b/test/graph/matching.cpp
@@ -1,6 +1,6 @@
 #include "../util.h"
 namespace tutte {
-void gauss(int n, ll mod);
+vector<int> gauss(vector<vector<ll>> &mat);
 #include <graph/matching.cpp>
 #include <math/shortModInv.cpp>
 #include <math/lgsFp.cpp>
@@ -15,19 +15,19 @@ void stress_test() {
 
 		GM blossom(n);
 		srand(Random::rng());
-		tutte::adj.assign(n, {});
+		vector<vector<int>> adj(n);
 
 		Graph<NoData> g(n);
 		g.erdosRenyi(m);
 		g.forEdges([&](int a, int b){
-			tutte::adj[a].push_back(b);
-			tutte::adj[b].push_back(a);
+			adj[a].push_back(b);
+			adj[b].push_back(a);
 
 			blossom.adj[a].push_back(b);
 			blossom.adj[b].push_back(a);
 		});
 
-		ll got = tutte::max_matching();
+		ll got = tutte::max_matching(adj);
 		ll expected = blossom.match();
 
 		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
@@ -43,14 +43,14 @@ void performance_test() {
 	Graph<NoData> g(N);
 	g.erdosRenyi(M);
 	srand(Random::rng());
-	tutte::adj.assign(N, {});
+	vector<vector<int>> adj(N);
 	g.forEdges([&](int a, int b){
-			tutte::adj[a].push_back(b);
-			tutte::adj[b].push_back(a);
+			adj[a].push_back(b);
+			adj[b].push_back(a);
 	});
 
 	t.start();
-	hash_t hash = tutte::max_matching();
+	hash_t hash = tutte::max_matching(adj);
 	t.stop();
 	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
 	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
diff --git a/test/math/lgsFp.cpp b/test/math/lgsFp.cpp
index 9c7bda8..376a067 100644
--- a/test/math/lgsFp.cpp
+++ b/test/math/lgsFp.cpp
@@ -1,6 +1,5 @@
 #include "../util.h"
 #include <math/shortModInv.cpp>
-vector<vector<ll>> mat;
 constexpr ll mod = 1'000'000'007;
 namespace lgs {
 	#include <math/lgsFp.cpp>
@@ -9,22 +8,18 @@ namespace lgs {
 
 vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) {
 	int n = ssize(m);
-	mat = m;
+	vector<vector<ll>> mat = m;
 	for (int i = 0; i < n; i++) {
 		if (ssize(mat[i]) != n) cerr << "error: no square matrix" << FAIL;
 		mat[i].resize(2*n);
 		mat[i][n+i] = 1;
 	}
-	lgs::gauss(ssize(mat), ssize(mat[0]));
-	vector<vector<ll>> res(m);
+	vector<int> pivots = lgs::gauss(mat);
 	for (int i = 0; i < n; i++) {
-		res[i] = vector<ll>(mat[i].begin() + n, mat[i].end());
-		for (int j = 0; j < n; j++) {
-			if (j != i && mat[i][j] != 0) cerr << "error: not full rank?" << FAIL;
-			if (j == i && mat[i][j] != 1) cerr << "error: not full rank?" << FAIL;
-		}
+		if (pivots[i] != i) cerr << "error: not full rank?" << FAIL;
+		mat[i].erase(begin(mat[i]), begin(mat[i]) + n);
 	}
-	return res;
+	return mat;
 }
 
 vector<vector<ll>> mul(const vector<vector<ll>>& a, const vector<vector<ll>>& b) {
@@ -53,18 +48,17 @@ void test_square() {
 
 		vector<vector<ll>> m(n);
 		for (auto& v : m) v = Random::integers<ll>(n, 0, mod);
-		mat = m;
-		lgs::gauss(ssize(mat), ssize(mat[0]));
+		lgs::gauss(m);
 
 		for (int i = 0; i < n; i++) {
 			for (int j = 0; j < n; j++) {
-				hash += mat[i][j];
+				hash += m[i][j];
 			}
 		}
 
 		queries += n;
 	}
-	cerr << "tested sqaures: " << queries << " (hash: " << hash << ")" << endl;;
+	cerr << "tested squares: " << queries << " (hash: " << hash << ")" << endl;;
 }
 
 void stress_test_inv() {
@@ -82,8 +76,7 @@ void stress_test_inv() {
 
 		for (int i = 0; i < n; i++) {
 			for (int j = 0; j < n; j++) {
-				if (i == j && prod[i][j] != 1) cerr << "error: not inverted" << FAIL;
-				if (i != j && prod[i][j] != 0) cerr << "error: not inverted" << FAIL;
+				if (prod[i][j] != (i == j)) cerr << "error: not inverted" << FAIL;
 			}
 		}
 
@@ -98,15 +91,14 @@ void performance_test() {
 
 	vector<vector<ll>> m(N);
 	for (auto& v : m) v = Random::integers<ll>(N, 0, mod);
-	mat = m;
 
 	t.start();
-	lgs::gauss(ssize(mat), ssize(mat[0]));
+	lgs::gauss(m);
 	t.stop();
 	hash_t hash = 0;
 	for (int i = 0; i < N; i++) {
 		for (int j = 0; j < N; j++) {
-			hash += mat[i][j];
+			hash += m[i][j];
 		}
 	}
 	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;