1 files changed, 87 insertions, 0 deletions
diff --git a/test/graph/euler.cpp b/test/graph/euler.cpp
new file mode 100644
index 0000000..6666040
--- /dev/null
+++ b/test/graph/euler.cpp
@@ -0,0 +1,87 @@
+#include "../util.h"
+struct Euler {
+	Euler(int n) : idx(n), validIdx(n) {}
+#include <graph/euler.cpp>
+};
+
+Euler eulerGraph(int n, int m) {
+	Euler res(n);
+
+	Graph<NoData> g(n);
+	g.tree();
+	g.forEdges([&](int a, int b) {
+		res.addEdge(a, b);
+	});
+
+	for (int i = n-1; i < m; i++) {
+		int a = Random::integer<int>(0, n);
+		int b = Random::integer<int>(0, n);
+		res.addEdge(a, b);
+	}
+	int last = -1;
+	for (int i = 0; i < n; i++) {
+		if (sz(res.idx[i]) % 2 != 0) {
+			if (last >= 0) {
+				res.addEdge(last, i);
+				last = -1;
+			} else {
+				last = i;
+			}
+		}
+	}
+	if (last >= 0) cerr << "FAIL" << FAIL;
+
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 200'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+		int m = Random::integer<int>(n-1, 200);
+
+		auto g = eulerGraph(n, m);
+		
+		vector<vector<int>> expected(n);
+		for (int i = 0; i < n; i++) {
+			for (int j : g.idx[i]) {
+				expected[i].push_back(g.to[j]);
+			}
+			sort(all(expected[i]));
+		}
+
+		g.euler(0);
+		vector<vector<int>> got(n);
+		if (g.cycle.front() != g.cycle.back()) cerr << "error: not cyclic" << FAIL;
+		for (int i = 1; i < sz(g.cycle); i++) {
+			int a = g.cycle[i-1];
+			int b = g.cycle[i];
+			got[a].push_back(b);
+			got[b].push_back(a);
+		}
+		for (auto& v : got) sort(all(v));
+
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 100'000;
+constexpr int M = 1'000'000;
+void performance_test() {
+	timer t;
+	auto g = eulerGraph(N, M);
+	t.start();
+	g.euler(0);
+	t.stop();
+	hash_t hash = 0;
+	for (int x : g.cycle) hash += x;
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}