summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--content/graph/matching.cpp17
-rw-r--r--content/math/lgsFp.cpp13
-rw-r--r--test/graph/blossom.cpp10
-rw-r--r--test/graph/matching.cpp18
-rw-r--r--test/math/lgsFp.cpp30
5 files changed, 39 insertions, 49 deletions
diff --git a/content/graph/matching.cpp b/content/graph/matching.cpp
index 3619d7c..f0f34a3 100644
--- a/content/graph/matching.cpp
+++ b/content/graph/matching.cpp
@@ -1,22 +1,17 @@
-constexpr int MOD=1'000'000'007, I=10;
-vector<vector<ll>> adj, mat;
+constexpr int mod = 1'000'000'007, I = 10;
-int max_matching() {
+int max_matching(const vector<vector<int>> &adj) {
int ans = 0;
- mat.assign(ssize(adj), {});
+ vector<vector<ll>> mat(ssize(adj));
for (int _ = 0; _ < I; _++) {
for (int v = 0; v < ssize(adj); v++) {
mat[v].assign(ssize(adj), 0);
for (int u : adj[v]) {
if (u < v) {
- mat[v][u] = rand() % (MOD - 1) + 1;
- mat[u][v] = MOD - mat[v][u];
+ mat[v][u] = rand() % (mod - 1) + 1;
+ mat[u][v] = mod - mat[v][u];
}}}
- gauss(ssize(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@
- int rank = 0;
- for (auto& row : mat) {
- if (*ranges::max_element(row) != 0) rank++;
- }
+ int rank = ssize(gauss(mat)); // LGS @\sourceref{math/lgsFp.cpp}@
ans = max(ans, rank / 2);
}
return ans;
diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp
index 4c12477..5028782 100644
--- a/content/math/lgsFp.cpp
+++ b/content/math/lgsFp.cpp
@@ -1,6 +1,7 @@
-vector<int> pivots; // ith pivot is in ith row
-void gauss(int n, int m) {
- for (int r = 0, c = 0; c < m; c++) {
+vector<int> gauss(vector<vector<ll>> &mat) {
+ int n = ssize(mat), m = ssize(mat[0]);
+ vector<int> pivots; // ith pivot is in ith row
+ for (int r = 0, c = 0; r < n && c < m; c++) {
for (int i = r; i < n; i++) {
if (mat[i][c] != 0){
swap(mat[r], mat[i]);
@@ -16,5 +17,7 @@ void gauss(int n, int m) {
mat[i][j] = (mat[i][j] - f*mat[r][j] % mod + mod) % mod;
}}
pivots.push_back(c);
- if (++r == n) break;
-}} // no solution if pivots.back() == m-1
+ r++;
+ }
+ return pivots; // no solution if pivots.back() == m-1
+}
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;
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 11:59:44 +0000