From 85b31124a07fa30111bda10f2ed958420f7ff575 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 20 Jul 2017 11:28:29 +0200 Subject: Removing unnecessary implication in OR-case --- graph/2sat.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) 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); } -- cgit v1.2.3 From a8a76010ed04bc931a09121847a93c3ca468e41a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 22 Jul 2017 12:28:21 +0200 Subject: Update articulationPoints.cpp fixed articulation points for disconnected graphs and automaticly set isArt for roots --- graph/articulationPoints.cpp | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-) diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp index aa73486..460919d 100644 --- a/graph/articulationPoints.cpp +++ b/graph/articulationPoints.cpp @@ -1,13 +1,13 @@ // Laufzeit: O(|V|+|E|) -vector< vector > adjlist; +vector> adjlist; vector isArt; vector d, low; -int counter, root; // root >= 2 <=> Wurzel Artikulationspunkt +int counter, root, rootCount; // root >= 2 <=> Wurzel Artikulationspunkt vector 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]) { @@ -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); isArtPoint.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; +}}} -- cgit v1.2.3 From ea229a62473986aa76edf9b890c7c3592ef27b46 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 22 Jul 2017 12:30:58 +0200 Subject: Update articulationPoints.cpp updated coments --- graph/articulationPoints.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp index 460919d..7b81c91 100644 --- a/graph/articulationPoints.cpp +++ b/graph/articulationPoints.cpp @@ -2,7 +2,7 @@ vector> adjlist; vector isArt; vector d, low; -int counter, root, rootCount; // root >= 2 <=> Wurzel Artikulationspunkt +int counter, root, rootCount; // rootCount >= 2 <=> root Artikulationspunkt vector bridges; // Nur fuer Brücken. void dfs(int v, int parent = -1) { -- cgit v1.2.3 From 4576d70b03ebb89d7747541bafa1e9018a39699b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 22 Jul 2017 14:09:47 +0200 Subject: Update articulationPoints.cpp root has an other calculation for isArt --- graph/articulationPoints.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp index 7b81c91..e7139d0 100644 --- a/graph/articulationPoints.cpp +++ b/graph/articulationPoints.cpp @@ -12,7 +12,7 @@ void dfs(int v, int parent = -1) { 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) { -- cgit v1.2.3 From 1f86a9097bb05c227dfc11a6739a4970d7b42360 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 28 Jul 2017 01:03:43 +0200 Subject: implemented new bitonic tsp algorithm this algorithm technically can be used to to solve bitonic tsp with linear space (by calculating dist[i][j] on the fly) it should be easier to use, a little bit quicker and is able reconstruct the used tour(maybe there is an easier way to reconstruct it?) --- graph/bitonicTSP.cpp | 47 +++++++++++++++++++++++++++++++++-------------- 1 file changed, 33 insertions(+), 14 deletions(-) diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp index bf01f9e..478362d 100644 --- a/graph/bitonicTSP.cpp +++ b/graph/bitonicTSP.cpp @@ -1,16 +1,35 @@ -// Laufzeit: O(|V|^2) -vector< vector > dp; // Initialisiere mit -1 -vector< vector > dist; // Initialisiere mit Entfernungen zwischen Punkten. -vector lr, rl; // Links-nach-rechts und rechts-nach-links Pfade. -int n; // #Knoten +// Laufzeit: O(n^2) +vector> dist; // Initialisiere mit Entfernungen zwischen Punkten. -// 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); +void bitonicTSP() { + vector dp(dist.size(), HUGE_VAL); + vector pre(dist.size()); // nur für Tour + dp[0] = 0, dp[1] = 2 * dist[0][1], pre[1] = 0; + for (unsigned int i = 2; i < dist.size(); i++) { + double link = 0; + for (int j = i - 2; j >= 0; j--) { + link += dist[j + 1][j + 2]; + double opt = link + dist[j][i] + dp[j + 1] - dist[j][j + 1]; + if (opt < dp[i]) { + dp[i] = opt; + pre[i] = j; + }}} + // return dp[dist.size() - 1]; // Länger der Tour + + int n = dist.size() - 1; + vector lt, ut; + lt.push_back(n), lt.push_back(n - 1); + int j; + do { + j = pre[n]; + (lt.back() == n ? lt : ut).push_back(j); + for (int i = n - 1; i > j + 1; i--) { + (lt.back() == i ? lt : ut).push_back(i - 1); + } + n = j + 1; + } while(j != 0); + lt.push_back(0); + reverse(lt.begin(), lt.end()); + lt.insert(lt.end(), ut.begin(), ut.end()); + //return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position. } -- cgit v1.2.3 From ff4b56d3bbd9b512a2963288712116d9a2aeeb18 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 28 Jul 2017 18:32:18 +0200 Subject: fixed last inserted edge --- graph/bitonicTSP.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp index 478362d..babddbd 100644 --- a/graph/bitonicTSP.cpp +++ b/graph/bitonicTSP.cpp @@ -28,7 +28,7 @@ void bitonicTSP() { } n = j + 1; } while(j != 0); - lt.push_back(0); + (lt.back() == 1 ? lt : ut).push_back(0); reverse(lt.begin(), lt.end()); lt.insert(lt.end(), ut.begin(), ut.end()); //return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position. -- cgit v1.2.3 From c7c2ee8604b84227be8f1b727930cf544efe2fcc Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 29 Jul 2017 11:44:53 +0200 Subject: reimplemented old dp solution and added path reconstruction --- graph/bitonicTSP.cpp | 54 +++++++++++++++++++++++----------------------------- 1 file changed, 24 insertions(+), 30 deletions(-) diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp index babddbd..f607f2c 100644 --- a/graph/bitonicTSP.cpp +++ b/graph/bitonicTSP.cpp @@ -1,35 +1,29 @@ // Laufzeit: O(n^2) vector> dist; // Initialisiere mit Entfernungen zwischen Punkten. +vector> dp; +vector> choice; -void bitonicTSP() { - vector dp(dist.size(), HUGE_VAL); - vector pre(dist.size()); // nur für Tour - dp[0] = 0, dp[1] = 2 * dist[0][1], pre[1] = 0; - for (unsigned int i = 2; i < dist.size(); i++) { - double link = 0; - for (int j = i - 2; j >= 0; j--) { - link += dist[j + 1][j + 2]; - double opt = link + dist[j][i] + dp[j + 1] - dist[j][j + 1]; - if (opt < dp[i]) { - dp[i] = opt; - pre[i] = j; - }}} - // return dp[dist.size() - 1]; // Länger der Tour +double get(int p1, int p2) { + 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); + choice[p1][p2] = tryLR < tryRL; + return dp[p1][p2] = min(tryLR, tryRL); +} - int n = dist.size() - 1; - vector lt, ut; - lt.push_back(n), lt.push_back(n - 1); - int j; - do { - j = pre[n]; - (lt.back() == n ? lt : ut).push_back(j); - for (int i = n - 1; i > j + 1; i--) { - (lt.back() == i ? lt : ut).push_back(i - 1); - } - n = j + 1; - } while(j != 0); - (lt.back() == 1 ? lt : ut).push_back(0); - reverse(lt.begin(), lt.end()); - lt.insert(lt.end(), ut.begin(), ut.end()); - //return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position. +void bitonicTour() { + dp = vector>(dist.size(), vector(dist.size(), -1)); + choice = vector>(dist.size(), vector(dist.size())); + get(0, 0); + // return dp[0][0]; // Länger der Tour + vector lr = {0}, rl = {0}; + for (int p1 = 0, p2 = 0, v; (v = max(p1, p2) + 1) < dist.size();) { + if (choice[p1][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. } -- cgit v1.2.3 From d38ab77bc7f61868430bf49b8306ffb69454c83d Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 29 Jul 2017 17:34:56 +0200 Subject: reincluded bitonic tsp --- graph/graph.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/graph/graph.tex b/graph/graph.tex index 937b976..a72c885 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -110,6 +110,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} -- cgit v1.2.3 From dc068beb30a7f257640178dcd00512ed6594a061 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 29 Jul 2017 17:35:20 +0200 Subject: removed todo --- graph/graph.tex | 1 - 1 file changed, 1 deletion(-) diff --git a/graph/graph.tex b/graph/graph.tex index a72c885..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} -- cgit v1.2.3 From dc1014bf6441d8bd61d4257fc481394736491da7 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 30 Jul 2017 18:04:38 +0200 Subject: simplified code --- graph/bitonicTSP.cpp | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp index f607f2c..9e4fac1 100644 --- a/graph/bitonicTSP.cpp +++ b/graph/bitonicTSP.cpp @@ -1,25 +1,22 @@ // Laufzeit: O(n^2) vector> dist; // Initialisiere mit Entfernungen zwischen Punkten. vector> dp; -vector> choice; double get(int p1, int p2) { 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); - choice[p1][p2] = tryLR < tryRL; return dp[p1][p2] = min(tryLR, tryRL); } void bitonicTour() { dp = vector>(dist.size(), vector(dist.size(), -1)); - choice = vector>(dist.size(), vector(dist.size())); get(0, 0); // return dp[0][0]; // Länger der Tour vector lr = {0}, rl = {0}; for (int p1 = 0, p2 = 0, v; (v = max(p1, p2) + 1) < dist.size();) { - if (choice[p1][p2]) { + if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) { lr.push_back(v); p1 = v; } else { rl.push_back(v); p2 = v; -- cgit v1.2.3