From 07a1c4f87dcccbfe2ca4fbbc100a07c9be801502 Mon Sep 17 00:00:00 2001 From: pjungeblut Date: Thu, 30 Oct 2014 19:26:30 +0100 Subject: SCCS added, seperated from 2-SAT --- graph/edmondsKarp.cpp | 34 +++++++++++++++++++++++ graph/graph.tex | 7 +++++ graph/scc.cpp | 54 +++++++++++++++++++++++++++++++++++++ maxFlow/edmondsKarp.cpp | 34 ----------------------- maxFlow/maxFlow.tex | 4 --- maxFlow/q.log | 25 ----------------- sonstiges/.2sat.cpp.kate-swp | Bin 0 -> 325 bytes sonstiges/2sat.cpp | 63 ------------------------------------------- sonstiges/sonstiges.tex | 7 ++++- tcr.pdf | Bin 81835 -> 111986 bytes tcr.tex | 2 +- 11 files changed, 102 insertions(+), 128 deletions(-) create mode 100644 graph/edmondsKarp.cpp create mode 100644 graph/graph.tex create mode 100644 graph/scc.cpp delete mode 100644 maxFlow/edmondsKarp.cpp delete mode 100644 maxFlow/maxFlow.tex delete mode 100644 maxFlow/q.log create mode 100644 sonstiges/.2sat.cpp.kate-swp delete mode 100644 sonstiges/2sat.cpp diff --git a/graph/edmondsKarp.cpp b/graph/edmondsKarp.cpp new file mode 100644 index 0000000..26c5b0d --- /dev/null +++ b/graph/edmondsKarp.cpp @@ -0,0 +1,34 @@ +int s, t, f; //source, target, single flow +int res[MAX_V][MAX_V]; //adj-matrix +vector< vector > adjList; +int p[MAX_V]; //bfs spanning tree + +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; +}} + +int maxFlow() { //first inititalize res, adjList, s and t + int mf = 0; + while (true) { + f = 0; + bitset vis; vis[s] = true; + queue 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); //add found path to max flow + if (f == 0) break; + mf += f; + } + return mf; +} \ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex new file mode 100644 index 0000000..1c37bc7 --- /dev/null +++ b/graph/graph.tex @@ -0,0 +1,7 @@ +\section{Graph} + +\subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} +\lstinputlisting{graph/scc.cpp} + +\subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} +\lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file diff --git a/graph/scc.cpp b/graph/scc.cpp new file mode 100644 index 0000000..b33616b --- /dev/null +++ b/graph/scc.cpp @@ -0,0 +1,54 @@ +int counter, sccCounter, n; //n == number of vertices +vector visited, inStack; +vector< vector > adjlist; +vector d, low, sccs; +stack s; + +void visit(int v) { + visited[v] = true; + d[v] = counter; + low[v] = counter; + counter++; + inStack[v] = true; + s.push(v); + + for (int i = 0; i < (int)adjlist[v].size(); i++) { + int u = adjlist[v][i]; + if (!visited[u]) { + visit(u); + low[v] = min(low[v], low[u]); + } else if (inStack[u]) { + low[v] = min(low[v], low[u]); + } + } + + if (d[v] == low[v]) { + int u; + do { + u = s.top(); + s.pop(); + inStack[u] = false; + sccs[u] = sccCounter; + } while(u != v); + sccCounter++; + } +} + +void scc() { + //read adjlist + + visited.clear(); visited.assign(n, false); + d.clear(); d.resize(n); + low.clear(); low.resize(n); + inStack.clear(); inStack.assign(n, false); + sccs.clear(); sccs.resize(n); + + counter = 0; + sccCounter = 0; + for (i = 0; i < n; i++) { + if (!visited[i]) { + visit(i); + } + } + //sccs has the component for each vertex +} \ No newline at end of file diff --git a/maxFlow/edmondsKarp.cpp b/maxFlow/edmondsKarp.cpp deleted file mode 100644 index ccfb1d2..0000000 --- a/maxFlow/edmondsKarp.cpp +++ /dev/null @@ -1,34 +0,0 @@ -int s, t, f; //source, target, single flow -int res[MAX_V][MAX_V]; //adj-matrix -vector< vector > adjList; -int p[MAX_V]; //bfs spanning tree - -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; -}} - -nt maxFlow() { //first inititalize res, adjList, s and t - int mf = 0; - while (true) { - f = 0; - bitset vis; vis[s] = true; - queue 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); //add found path to max flow - if (f == 0) break; - mf += f; - } - return maxFlow; -} \ No newline at end of file diff --git a/maxFlow/maxFlow.tex b/maxFlow/maxFlow.tex deleted file mode 100644 index a88e5ff..0000000 --- a/maxFlow/maxFlow.tex +++ /dev/null @@ -1,4 +0,0 @@ -\section{Max Flows} -\subsection{\textsc{Edmonds-Karp}-Algorithmus} - -\lstinputlisting{maxFlow/edmondsKarp.cpp} \ No newline at end of file diff --git a/maxFlow/q.log b/maxFlow/q.log deleted file mode 100644 index 2a742c3..0000000 --- a/maxFlow/q.log +++ /dev/null @@ -1,25 +0,0 @@ -This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2014.5.4) 25 OCT 2014 13:42 -entering extended mode - restricted \write18 enabled. - %&-line parsing enabled. -**tcr.tex -(/usr/share/texlive/texmf-dist/tex/latex/tools/q.tex -LaTeX2e <2011/06/27> -Babel <3.9h> and hyphenation patterns for 7 languages loaded. -File ignored -) -! Emergency stop. -<*> tcr.tex - -*** (job aborted, no legal \end found) - - -Here is how much of TeX's memory you used: - 7 strings out of 494976 - 248 string characters out of 6179138 - 46219 words of memory out of 5000000 - 3331 multiletter control sequences out of 15000+600000 - 3640 words of font info for 14 fonts, out of 8000000 for 9000 - 14 hyphenation exceptions out of 8191 - 5i,0n,1p,87b,8s stack positions out of 5000i,500n,10000p,200000b,80000s -! ==> Fatal error occurred, no output PDF file produced! diff --git a/sonstiges/.2sat.cpp.kate-swp b/sonstiges/.2sat.cpp.kate-swp new file mode 100644 index 0000000..b688b2e Binary files /dev/null and b/sonstiges/.2sat.cpp.kate-swp differ diff --git a/sonstiges/2sat.cpp b/sonstiges/2sat.cpp deleted file mode 100644 index 627e484..0000000 --- a/sonstiges/2sat.cpp +++ /dev/null @@ -1,63 +0,0 @@ -vector< vector > adjlist; //adjazenzliste -vector sccs; //speichert die gefundenen SCCs -vector visited; //welcher Knoten ist schon besucht worden (in der DFS) -vector inStack; //ist Knoten gerade im Stack -vector d; //discovery time -vector low; //wie weit hoch geht's im Tiefensuchbaum -int counter; //Zaehler fuer discovery time -stack st; //der Stack -int sccCounter; //Zaehler fuer SCCs - -//Tiefensuche, die starke Zusammenhangskomponenten findet -void visit(int v) { - visited[v] = true; - d[v] = counter; - low[v] = counter; - counter++; - st.push(v); - inStack[v] = true; - - for (int i = 0; i < (int)adjlist[v].size(); i++) { - int w = adjlist[v][i]; - - if (!visited[w]) { - visit(w); - low[v] = min(low[v], low[w]); - } else if (inStack[w]) { - low[v] = min(low[v], low[w]); - } - } - - if (low[v] == d[v]) { - int next; - do { - next = st.top(); - st.pop(); - sccs[next] = sccCounter; - inStack[next] = false; - } while (next != v); - - sccCounter++; - } -} - -void solve() { - //adjlist initialisieren - //(a || b) wird zu (!a => b) und (!b => a) - - visited.clear(); visited.assign(adjlist.size(), false); - inStack.clear(); inStack.assign(adjlist.size(), false); - d.clear(); d.assign(adjlist.size(), false); - low.clear(); low.assign(adjlist.size(), false); - sccs.clear(); sccs.resize(adjlist.size()); - - counter = 0; - sccCounter = 0; - for (i = 0; i < (int)adjlist.size(); i++) { - if (!visited[i]) { - visit(i); - sccCounter++; - } - } - // genau dann loesbar, wenn keine Variable in gleicher SCC wie Negation ist -} \ No newline at end of file diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex index 0befff3..09ea14c 100644 --- a/sonstiges/sonstiges.tex +++ b/sonstiges/sonstiges.tex @@ -1,4 +1,9 @@ \section{Sonstiges} \subsection{2-SAT} -\lstinputlisting{sonstiges/2sat.cpp} \ No newline at end of file +\begin{enumerate} + \item Bedingungen in 2-CNF formulieren. + \item Implikationsgraph bauen, $\left(a \vee b\right)$ wird zu $\neg a \Rightarrow b$ und $\neg b \Rightarrow a$. + \item Finde die starken Zusammenhangskomponenten. + \item Genau dann lösbar, wenn keine Variable mit ihrer Negation in einer SCC liegt. +\end{enumerate} \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index db1ab6c..09ae39b 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 11aeecf..9b43116 100644 --- a/tcr.tex +++ b/tcr.tex @@ -47,7 +47,7 @@ \tableofcontents \newpage -\input{maxFlow/maxFlow} +\input{graph/graph} \input{geometry/geometry} \input{sonstiges/sonstiges} -- cgit v1.2.3