From c97d2d14c071d19f9310839b6f9b2d2bdebf363b Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Tue, 28 Feb 2023 17:27:39 +0100
Subject: simplified tree isomorphism

---
 graph/graph.tex           |   3 ++-
 graph/treeIsomorphism.cpp |  56 +++++++++++++---------------------------------
 tcr.pdf                   | Bin 648971 -> 646662 bytes
 3 files changed, 17 insertions(+), 42 deletions(-)

diff --git a/graph/graph.tex b/graph/graph.tex
index 47f1d75..ab8d157 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -39,10 +39,11 @@
 
 \begin{algorithm}{Baum-Isomorphie}
 	\begin{methods}
-		\method{getTreeLabel}{berechnet kanonischen Namen für einen Baum}{\abs{V}}
+		\method{treeLabel}{berechnet kanonischen Namen für einen Baum}{\abs{V}\*\log(\abs{V})}
 	\end{methods}
 	\sourcecode{graph/treeIsomorphism.cpp}
 \end{algorithm}
+\clearpage
 
 \subsection{Kürzeste Wege}
 
diff --git a/graph/treeIsomorphism.cpp b/graph/treeIsomorphism.cpp
index f3e147b..7a1be5b 100644
--- a/graph/treeIsomorphism.cpp
+++ b/graph/treeIsomorphism.cpp
@@ -1,41 +1,15 @@
-vector<vector<vector<int>>>
-getTreeLabel(const vector<vector<int>>& adj, int root) {
-	vector<vector<int>> level = {{root}};
-	vector<int> dist(sz(adj), -1);
-	dist[root] = 0;
-	queue<int> q;
-	q.push(root);
-	while (!q.empty()) {
-		int c = q.front();
-		q.pop();
-		for (int n : adj[c]) {
-			if (dist[n] < 0) {
-				dist[n] = dist[c] + 1;
-				if (sz(level) <= dist[n]) level.push_back({});
-				level[dist[n]].push_back(n);
-				q.push(n);
-	}}}
-	
-	vector<vector<vector<int>>> levelLabels(sz(level));
-	vector<int> shortLabel(sz(adj));
-	for (int l = sz(level) - 1; l >= 0; l--) {
-		vector<pair<vector<int>, int>> tmpLabels;
-		for (int v : level[l]) {
-			vector<int> label;
-			for (int n : adj[v]) {
-				if (dist[n] > dist[v]) {
-					label.push_back(shortLabel[n]);
-			}}
-			sort(all(label));
-			tmpLabels.push_back({label, v});
-		}
-		sort(all(tmpLabels));
-		vector<int>& last = tmpLabels[0].first;
-		int curId = 0;
-		for (auto& e : tmpLabels) {
-			levelLabels[l].push_back(e.first);
-			if (e.first != last) curId++, last = e.first;
-			shortLabel[e.second] = curId;
-	}}
-	return levelLabels;
-} 
+vector<vector<int>> adj;
+map<vector<int>, int> known;
+
+int treeLabel(int root, int p = -1) {
+	vector<int> children;
+	for (int x : adj[root]) {
+		if (x == p) continue;
+		children.push_back(treeLabel(x, root));
+	}
+	sort(all(children));
+	if (known.find(children) == known.end()) {
+		known[children] = sz(known);
+	}
+	return known[children];
+}
diff --git a/tcr.pdf b/tcr.pdf
index ed22578..c99511c 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3