From 59bea75c7c785e9012b0f3d677b9afbf93818fb4 Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Sun, 8 Jun 2025 23:30:29 +0200
Subject: make SCC a struct, and minor 2SAT changes

---
 test/graph/2sat.cpp     | 10 +++-------
 test/graph/2sat.cpp.awk |  6 ------
 test/graph/scc.cpp      | 24 ++++++++++++------------
 3 files changed, 15 insertions(+), 25 deletions(-)
 delete mode 100644 test/graph/2sat.cpp.awk

(limited to 'test/graph')

diff --git a/test/graph/2sat.cpp b/test/graph/2sat.cpp
index cf37131..e969364 100644
--- a/test/graph/2sat.cpp
+++ b/test/graph/2sat.cpp
@@ -25,7 +25,7 @@ struct RandomClause {
 		return false;
 	}
 
-	void add(sat2& sat) const {
+	void add(SAT2& sat) const {
 		int va = a;
 		int vb = b;
 		if (type == 0) sat.addImpl(va, vb);
@@ -80,9 +80,8 @@ void stress_test() {
 		vector<RandomClause> clauses;
 		for (int i = 0; i < m; i++) clauses.emplace_back(n);
 
-		sat2 sat(n);
+		SAT2 sat(n);
 		for (auto& c : clauses) c.add(sat);
-		adj = sat.adj;
 
 		bool got = sat.solve();
 		bool expected = naive(n, clauses);
@@ -113,11 +112,8 @@ void performance_test() {
 	vector<RandomClause> clauses;
 	for (int i = 0; i < M; i++) clauses.emplace_back(N);
 	t.start();
-	sat2 sat(N);
+	SAT2 sat(N);
 	for (auto& c : clauses) c.add(sat);
-	t.stop();
-	adj = sat.adj;
-	t.start();
 	hash_t hash = sat.solve();
 	t.stop();
 	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
diff --git a/test/graph/2sat.cpp.awk b/test/graph/2sat.cpp.awk
deleted file mode 100644
index d0215d8..0000000
--- a/test/graph/2sat.cpp.awk
+++ /dev/null
@@ -1,6 +0,0 @@
-/scc variablen/ {
-    print;
-    print "\tvector<vector<int>> adj;";
-    next
-}
-{ print }
diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp
index 46ad201..bc52d7e 100644
--- a/test/graph/scc.cpp
+++ b/test/graph/scc.cpp
@@ -9,11 +9,11 @@ void stress_test() {
 		Graph<NoData, true> g(n);
 		g.erdosRenyi(m);
 
-		adj.assign(n, {});
-		g.forEdges([](int a, int b){
+		vector<vector<int>> adj(n);
+		g.forEdges([&](int a, int b){
 			adj[a].push_back(b);
 		});
-		scc();
+		SCC scc(adj);
 
 		auto reach = [&](int a) -> vector<bool> {
 			vector<bool> seen(n);
@@ -29,9 +29,9 @@ void stress_test() {
 		};
 
 		vector<int> seen(n);
-		for (int i = 0; i < ssize(sccs); i++) {
-			for (int v: sccs[i]) {
-				if (idx[v] != i) cerr << v << " is in scc " << i << ", but idx[" << v << "] = " << idx[v] << FAIL;
+		for (int i = 0; i < ssize(scc.sccs); i++) {
+			for (int v: scc.sccs[i]) {
+				if (scc.idx[v] != i) cerr << v << " is in scc " << i << ", but idx[" << v << "] = " << scc.idx[v] << FAIL;
 				seen[v]++;
 			}
 		}
@@ -40,9 +40,9 @@ void stress_test() {
 			if (seen[a] != 1) cerr << a << " occurs " << seen[a] << " times in sccs" << FAIL;
 			vector<bool> reacha = reach(a);
 			for (int b = 0; b < n; b++) {
-				if (idx[a] == idx[b]) {
+				if (scc.idx[a] == scc.idx[b]) {
 					if (!reacha[b]) cerr << a << " and " << b << " should be in different SCCs" << FAIL;
-				} else if (idx[a] < idx[b]) {
+				} else if (scc.idx[a] < scc.idx[b]) {
 					if (reacha[b]) cerr << a << " should come before " << b << " in topological order" << FAIL;
 				}
 			}
@@ -58,16 +58,16 @@ void performance_test() {
 	timer t;
 	Graph<NoData, true> g(N);
 	g.erdosRenyi(M);
-	adj.assign(N, {});
-	g.forEdges([](int a, int b){
+	vector<vector<int>> adj(N);
+	g.forEdges([&](int a, int b){
 		adj[a].push_back(b);
 	});
 
 	t.start();
-	scc();
+	SCC scc(adj);
 	t.stop();
 	hash_t hash = 0;
-	for (int x : idx) hash += x;
+	for (int x : scc.idx) hash += x;
 	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
 	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
 }
-- 
cgit v1.2.3