gebaut

4 files changed, 120 insertions, 1 deletions

diff --git a/graph/LCA.cpp b/graph/LCA.cpp
new file mode 100644
index 0000000..b4e6bdd
--- /dev/null
+++ b/graph/LCA.cpp
@@ -0,0 +1,16 @@
+//RMQ muss hinzugefuegt werden!
+vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N);
+vector<vector<int>> graph(MAX_N);
+
+void initLCA(int gi, int d, int &c) {
+	visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++;
+	for(int gn : graph[gi]) {
+		initLCA(gn, d+1, c);
+		visited[c] = gi, depth[c] = d, c++;
+	}
+}
+//[a, b]
+int getLCA(int a, int b) {
+	return visited[queryRMQ(min(first[a], first[b]), max(first[a], first[b]))];
+}
+//=> int c = 0; initLCA(0,0,c); initRMQ(); done!
diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp
new file mode 100644
index 0000000..b99a286
--- /dev/null
+++ b/graph/articulationPoints.cpp
@@ -0,0 +1,47 @@
+vector< vector<int> > adjlist;
+vector<int> low;
+vector<int> d;
+vector<bool> isArtPoint;
+vector< vector<int> > bridges; //nur fuer Bruecken
+int counter = 0;
+
+void visit(int v, int parent) {
+	d[v] = low[v] = ++counter;
+	int numVisits = 0, maxlow = 0;
+	
+	for (vector<int>::iterator vit = adjlist[v].begin(); vit != adjlist[v].end(); vit++) {
+		if (d[*vit] == 0) {
+			numVisits++;
+			visit(*vit, v);
+			if (low[*vit] > maxlow) {
+				maxlow = low[*vit];
+			}
+			
+			if (low[*vit] > d[v]) { //nur fuer Bruecken
+				bridges[v].push_back(*vit); bridges[*vit].push_back(v);
+			}
+			
+			low[v] = min(low[v], low[*vit]);
+		} else {
+			if (d[*vit] < low[v]) {
+				low[v] = d[*vit];
+			}
+		}
+	}
+	
+	if (parent == -1) {
+		if (numVisits > 1) isArtPoint[v] = true;
+	} else {
+		if (maxlow >= d[v]) isArtPoint[v] = true;
+	}
+}
+
+void findArticulationPoints() {
+	low.clear(); low.resize(adjlist.size());
+	d.clear(); d.assign(adjlist.size(), 0);
+	isArtPoint.clear(); isArtPoint.assign(adjlist.size(), false);
+	bridges.clear(); isBridge.resize(adjlist.size()); //nur fuer Bruecken
+	for (int v = 0; v < (int)adjlist.size(); v++) {
+		if (d[v] == 0) visit(v, -1);
+	}
+}
\ No newline at end of file
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
diff --git a/graph/graph.tex b/graph/graph.tex
index 8d01e97..e3fd262 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,5 +1,8 @@
 \section{Graphen}
 
+\subsection{Lowest Common Ancestor}
+\lstinputlisting{graph/LCA.cpp}
+
 \subsection{Kürzeste Wege}
 
 \subsubsection{Algorithmus von \textsc{Dijkstra}}
@@ -17,5 +20,17 @@ Alle kürzesten Pfade im Graphen.
 \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
 \lstinputlisting{graph/scc.cpp}
 
+\subsection{Artikulationspunkte und Brücken}
+\lstinputlisting{graph/articulationPoints.cpp}
+
+\subsection{Eulertouren}
+\begin{itemize}
+	\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
+	\item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
+	\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.
+\end{itemize}
+\lstinputlisting{graph/euler.cpp}
+
 \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)}
-\lstinputlisting{graph/edmondsKarp.cpp}
\ No newline at end of file
+\lstinputlisting{graph/edmondsKarp.cpp}