From 4663f02b5df9713ce2d75b4f19bc6ca103f2d0ce Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc57.atis-stud.uni-karlsruhe.de>
Date: Sat, 22 Nov 2014 17:10:04 +0100
Subject: eulerzyklen

---
 graph/euler.cpp | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)
 create mode 100644 graph/euler.cpp

(limited to 'graph/euler.cpp')

diff --git a/graph/euler.cpp b/graph/euler.cpp
new file mode 100644
index 0000000..74b3399
--- /dev/null
+++ b/graph/euler.cpp
@@ -0,0 +1,41 @@
+vector< vector<int> > adjlist;
+vector< vector<int> > otherIdx;
+vector<int> cycle;
+vector<int> validIdx;
+
+void swapEdges(int n, int a, int b) { // Vertauscht Kanten mit Indizes a und b von Knoten n.
+	int neighA = adjlist[n][a];
+	int neighB = adjlist[n][b];
+	int idxNeighA = otherIdx[n][a];
+	int idxNeighB = otherIdx[n][b];
+	swap(adjlist[n][a], adjlist[n][b]);
+	swap(otherIdx[n][a], otherIdx[n][b]);
+	otherIdx[neighA][idxNeighA] = b;
+	otherIdx[neighB][idxNeighB] = a;
+}
+
+void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehoerige Rueckwaertskante).
+	int other = adjlist[n][i];
+	if (other == n) { //Schlingen
+		validIdx[n]++;
+		return;
+	}
+	int otherIndex = otherIdx[n][i];
+	validIdx[n]++;
+	if (otherIndex != validIdx[other]) {
+		swapEdges(other, otherIndex, validIdx[other]);
+	}
+	validIdx[other]++;
+}
+
+//findet Eulerzyklus an Knoten n startend
+//teste vorher, dass Graph zusammenhaengend ist! (isolierte Punkte sind ok)
+//teste vorher, ob Eulerzyklus ueberhaupt existiert!
+void euler(int n) {
+	while (validIdx[n] < (int)adjlist[n].size()) {
+		int nn = adjlist[n][validIdx[n]];
+		removeEdge(n, validIdx[n]);
+		euler(nn);
+	}
+	cycle.push_back(n); //Zyklus am Ende in cycle
+}
\ No newline at end of file
-- 
cgit v1.2.3