Improving Euler path code.

2 files changed, 12 insertions, 17 deletions

diff --git a/graph/euler.cpp b/graph/euler.cpp
index 6551ac3..a35ce13 100644
--- a/graph/euler.cpp
+++ b/graph/euler.cpp
@@ -1,21 +1,19 @@
 // Laufzeit: O(|V|+|E|)
-vector< vector<int> > adjlist;
-vector< vector<int> > otherIdx;
-vector<int> cycle;
-vector<int> validIdx;
+vector< vector<int> > adjlist, otherIdx;
+vector<int> cycle, 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];
+// Vertauscht Kanten mit Indizes a und b von Knoten n.
+void swapEdges(int n, int a, int b) {
+	int neighA = adjlist[n][a], neighB = adjlist[n][b];
+	int idxNeighA = otherIdx[n][a], 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 zugehörige Rückwärtskante).
+// Entfernt Kante i von Knoten n (und die zugehörige Rückwärtskante).
+void removeEdge(int n, int i) {
 	int other = adjlist[n][i];
 	if (other == n) { //Schlingen.
 		validIdx[n]++;
@@ -30,7 +28,7 @@ void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehÃ
 }
 
 // Findet Eulerzyklus an Knoten n startend.
-// Teste vorher, dass Graph zusammenhängend ist! Was ist mit isolierten Knoten?
+// Teste vorher, dass Graph zusammenhängend ist! Isolierten Knoten?
 // Teste vorher, ob Eulerzyklus überhaupt existiert!
 void euler(int n) {
 	while (validIdx[n] < (int)adjlist[n].size()) {
@@ -38,5 +36,5 @@ void euler(int n) {
 		removeEdge(n, validIdx[n]);
 		euler(nn);
 	}
-	cycle.push_back(n); // Zyklus am Ende in cycle (umgekehrte Reihenfolge).
+	cycle.push_back(n); // Zyklus in cycle in umgekehrter Reihenfolge.
 }
diff --git a/graph/graph.tex b/graph/graph.tex
index 77ee874..ac8e92b 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -48,6 +48,8 @@ Erkennt negative Zyklen.
 	\item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.}
 	\item Der Code unten läuft in Linearzeit.
 	Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher.
+	\item Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
+	Die Existenz muss separat geprüft werden.
 \end{itemize}
 \begin{lstlisting}
 VISIT(v):
@@ -57,11 +59,6 @@ VISIT(v):
 	print e
 \end{lstlisting}
 \lstinputlisting{graph/euler.cpp}
-\begin{itemize}
-	\item Die Ausgabe erfolgt in falscher Reihenfolge.
-	\item Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
-	Die Existenz muss separat geprüft werden.
-\end{itemize}
 
 \subsection{Lowest Common Ancestor}
 \lstinputlisting{graph/LCA.cpp}