diff options
| -rw-r--r-- | graph/2sat.cpp | 2 | ||||
| -rw-r--r-- | graph/articulationPoints.cpp | 22 | ||||
| -rw-r--r-- | graph/bitonicTSP.cpp | 36 | ||||
| -rw-r--r-- | graph/graph.tex | 5 |
4 files changed, 39 insertions, 26 deletions
diff --git a/graph/2sat.cpp b/graph/2sat.cpp index 99df78c..ab38b02 100644 --- a/graph/2sat.cpp +++ b/graph/2sat.cpp @@ -14,7 +14,7 @@ struct sat2 { adjlist[1^v2].push_back(1^v1); } void addEquiv(int v1, int v2) { addImpl(v1, v2); addImpl(v2, v1); } - void addOr(int v1, int v2) { addImpl(1^v1, v2); addImpl(1^v2, v1); } + void addOr(int v1, int v2) { addImpl(1^v1, v2); } void addXor(int v1, int v2) { addOr(v1, v2); addOr(1^v1, 1^v2); } void addTrue(int v1) { addImpl(1^v1, v1); } void addFalse(int v1) { addTrue(1^v1); } diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp index 4bd2243..fba08bb 100644 --- a/graph/articulationPoints.cpp +++ b/graph/articulationPoints.cpp @@ -1,18 +1,18 @@ // Laufzeit: O(|V|+|E|) -vector< vector<int> > adjlist; +vector<vector<int>> adjlist; vector<bool> isArt; vector<int> d, low; -int counter, root; // root >= 2 <=> Wurzel Artikulationspunkt +int counter, root, rootCount; // rootCount >= 2 <=> root Artikulationspunkt vector<ii> bridges; // Nur fuer Brücken. -void dfs(int v, int parent) { // Mit parent=-1 aufrufen. - d[v] = low[v] = counter++; - if (parent == 0) root++; +void dfs(int v, int parent = -1) { + d[v] = low[v] = ++counter; + if (parent == root) ++rootCount; for (auto w : adjlist[v]) { if (!d[w]) { dfs(w, v); - if (low[w] >= d[v]) isArt[v] = true; + if (low[w] >= d[v] && v != root) isArt[v] = true; if (low[w] > d[v]) bridges.push_back(ii(v, w)); low[v] = min(low[v], low[w]); } else if (w != parent) { @@ -20,10 +20,14 @@ void dfs(int v, int parent) { // Mit parent=-1 aufrufen. }}} void findArticulationPoints() { - counter = 1; // Nicht auf 0 setzen! + counter = 0; low.resize(adjlist.size()); d.assign(adjlist.size(), 0); isArt.assign(adjlist.size(), false); bridges.clear(); //nur fuer Bruecken - for (int v = 0; v < (int)adjlist.size(); v++) if (!d[v]) dfs(v, -1); -} + for (int v = 0; v < (int)adjlist.size(); v++) { + if (!d[v]) { + root = v; rootCount = 0; + dfs(v); + if (rootCount > 1) isArt[v] = true; +}}} diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp index bf01f9e..9e4fac1 100644 --- a/graph/bitonicTSP.cpp +++ b/graph/bitonicTSP.cpp @@ -1,16 +1,26 @@ -// Laufzeit: O(|V|^2) -vector< vector<double> > dp; // Initialisiere mit -1 -vector< vector<double> > dist; // Initialisiere mit Entfernungen zwischen Punkten. -vector<int> lr, rl; // Links-nach-rechts und rechts-nach-links Pfade. -int n; // #Knoten +// Laufzeit: O(n^2) +vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten. +vector<vector<double>> dp; -// get(0, 0) gibt die Länge der kürzesten bitonischen Route. double get(int p1, int p2) { - int v = max(p1, p2) + 1; - if (v == n - 1) return dist[p1][v] + dist[v][p2]; - if (dp[p1][p2] > -0.5) return dp[p1][p2]; - double tryLR = dist[p1][v] + get(v, p2), tryRl = dist[v][p2] + get(p1, v); - if (tryLR < tryRL) lr.push_back(v); // Baut die Pfade auf. Fügt v zu rl hinzu, falls beide gleich teuer. - else rl.push_back(v); // Änder das, falls nötig. - return min(tryLR, tryRL); + int v = max(p1, p2) + 1; + if (v == dist.size()) return dist[p1][v - 1] + dist[p2][v - 1]; + if (dp[p1][p2] >= 0.0) return dp[p1][p2]; + double tryLR = dist[p1][v] + get(v, p2), tryRL = dist[p2][v] + get(p1, v); + return dp[p1][p2] = min(tryLR, tryRL); +} + +void bitonicTour() { + dp = vector<vector<double>>(dist.size(), vector<double>(dist.size(), -1)); + get(0, 0); + // return dp[0][0]; // Länger der Tour + vector<int> lr = {0}, rl = {0}; + for (int p1 = 0, p2 = 0, v; (v = max(p1, p2) + 1) < dist.size();) { + if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) { + lr.push_back(v); p1 = v; + } else { + rl.push_back(v); p2 = v; + }} + lr.insert(lr.end(), rl.rbegin(), rl.rend()); + // return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position. } diff --git a/graph/graph.tex b/graph/graph.tex index 937b976..596c0d6 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -37,7 +37,6 @@ Erkennt negative Zyklen. \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} -% TODO (pjungeblut): This has errors for bridges! \subsection{Artikulationspunkte und Brücken} \lstinputlisting{graph/articulationPoints.cpp} @@ -110,6 +109,6 @@ Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling. % \subsection{TSP} % \lstinputlisting{graph/TSP.cpp} -% \subsection{Bitonic TSP} -% \lstinputlisting{graph/bitonicTSP.cpp} +\subsection{Bitonic TSP} +\lstinputlisting{graph/bitonicTSP.cpp} |