Removing Edmonds Karp since capacity scaling is faster.

2 files changed, 0 insertions, 39 deletions

diff --git a/graph/edmondsKarp.cpp b/graph/edmondsKarp.cpp
deleted file mode 100644
index dcfd85b..0000000
--- a/graph/edmondsKarp.cpp
+++ /dev/null
@@ -1,36 +0,0 @@
-// Laufzeit: O(|V|*|E|^2)
-int s, t, f; // Quelle, Senke, single flow
-int res[MAX_V][MAX_V];
-vector< vector<int> > adjlist;
-int p[MAX_V];
-
-void augment(int v, int minEdge) {
-	if (v == s) { f = minEdge; return; }
-	else if (p[v] != -1) {
-		augment(p[v], min(minEdge, res[p[v]][v]));
-		res[p[v]][v] -= f; res[v][p[v]] += f;
-}}
-
-// Initialisiere res, adjList, s und t.
-int maxFlow() {
-	int mf = 0;
-	while (true) {
-		f = 0;
-		bitset<MAX_V> vis; vis[s] = true;
-		queue<int> q; q.push(s);
-		memset(p, -1, sizeof(p));
-		while (!q.empty()) { // BFS
-			int u = q.front(); q.pop();
-			if (u == t) break;
-			for (int j = 0; j < (int)adjlist[u].size(); j++) {
-				int v = adjlist[u][j];
-				if (res[u][v] > 0 && !vis[v]) {
-					vis[v] = true; q.push(v); p[v] = u;
-		}}}
-		
-		augment(t, INF); // Pfad zu Fluss hinzufügen.
-		if (f == 0) break;
-		mf += f;
-	}
-	return mf;
-}
diff --git a/graph/graph.tex b/graph/graph.tex
index f23db82..8ac82e5 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -74,9 +74,6 @@ Erkennt negative Zyklen.
 
 \subsection{Max-Flow}
 
-\subsubsection{\textsc{Edmonds-Karp}-Algorithmus}
-\lstinputlisting{graph/edmondsKarp.cpp}
-
 \subsubsection{Capacity Scaling}
 \lstinputlisting{graph/capacityScaling.cpp}