From 04ca8f7bd16c0c855f604188d617a1bf2e8eacfd Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Thu, 13 Feb 2025 22:07:35 +0100 Subject: rename Dinic to Dinitz --- content/graph/dinicScaling.cpp | 57 -------------------------------------- content/graph/dinitzScaling.cpp | 57 ++++++++++++++++++++++++++++++++++++++ content/graph/graph.tex | 4 +-- content/other/other.tex | 2 +- test/graph/dinicScaling.cpp | 61 ----------------------------------------- test/graph/dinitzScaling.cpp | 61 +++++++++++++++++++++++++++++++++++++++++ test/graph/pushRelabel.cpp | 12 ++++---- 7 files changed, 127 insertions(+), 127 deletions(-) delete mode 100644 content/graph/dinicScaling.cpp create mode 100644 content/graph/dinitzScaling.cpp delete mode 100644 test/graph/dinicScaling.cpp create mode 100644 test/graph/dinitzScaling.cpp diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp deleted file mode 100644 index fd82296..0000000 --- a/content/graph/dinicScaling.cpp +++ /dev/null @@ -1,57 +0,0 @@ -struct Edge { - int to, rev; - ll f, c; -}; - -vector> adj; -int s, t; -vector pt, dist; - -void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); - adj[v].push_back({u, (int)ssize(adj[u]) - 1, 0, 0}); -} - -bool bfs(ll lim) { - dist.assign(ssize(adj), -1); - dist[s] = 0; - queue q({s}); - while (!q.empty() && dist[t] < 0) { - int v = q.front(); q.pop(); - for (Edge& e : adj[v]) { - if (dist[e.to] < 0 && e.c - e.f >= lim) { - dist[e.to] = dist[v] + 1; - q.push(e.to); - }}} - return dist[t] >= 0; -} - -ll dfs(int v, ll flow) { - if (v == t || flow == 0) return flow; - for (; pt[v] < ssize(adj[v]); pt[v]++) { - Edge& e = adj[v][pt[v]]; - if (dist[e.to] != dist[v] + 1) continue; - ll cur = dfs(e.to, min(e.c - e.f, flow)); - if (cur > 0) { - e.f += cur; - adj[e.to][e.rev].f -= cur; - return cur; - }} - return 0; -} - -ll maxFlow(int source, int target) { - s = source, t = target; - ll flow = 0; - // lim = 1 may be faster if capacities are small - for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { - while (bfs(lim)) { - pt.assign(ssize(adj), 0); - ll cur; - do { - cur = dfs(s, lim); - flow += cur; - } while (cur > 0); - }} - return flow; -} diff --git a/content/graph/dinitzScaling.cpp b/content/graph/dinitzScaling.cpp new file mode 100644 index 0000000..fd82296 --- /dev/null +++ b/content/graph/dinitzScaling.cpp @@ -0,0 +1,57 @@ +struct Edge { + int to, rev; + ll f, c; +}; + +vector> adj; +int s, t; +vector pt, dist; + +void addEdge(int u, int v, ll c) { + adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); + adj[v].push_back({u, (int)ssize(adj[u]) - 1, 0, 0}); +} + +bool bfs(ll lim) { + dist.assign(ssize(adj), -1); + dist[s] = 0; + queue q({s}); + while (!q.empty() && dist[t] < 0) { + int v = q.front(); q.pop(); + for (Edge& e : adj[v]) { + if (dist[e.to] < 0 && e.c - e.f >= lim) { + dist[e.to] = dist[v] + 1; + q.push(e.to); + }}} + return dist[t] >= 0; +} + +ll dfs(int v, ll flow) { + if (v == t || flow == 0) return flow; + for (; pt[v] < ssize(adj[v]); pt[v]++) { + Edge& e = adj[v][pt[v]]; + if (dist[e.to] != dist[v] + 1) continue; + ll cur = dfs(e.to, min(e.c - e.f, flow)); + if (cur > 0) { + e.f += cur; + adj[e.to][e.rev].f -= cur; + return cur; + }} + return 0; +} + +ll maxFlow(int source, int target) { + s = source, t = target; + ll flow = 0; + // lim = 1 may be faster if capacities are small + for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { + while (bfs(lim)) { + pt.assign(ssize(adj), 0); + ll cur; + do { + cur = dfs(s, lim); + flow += cur; + } while (cur > 0); + }} + return flow; +} diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 6e8e20b..0692d20 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -215,12 +215,12 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/pushRelabel.cpp} } -\subsubsection{\textsc{Dinic}'s Algorithm mit Capacity Scaling} +\subsubsection{\textsc{Dinitz}'s Algorithm mit Capacity Scaling} \begin{methods} \method{maxFlow}{doppelt so schnell wie \textsc{Ford-Fulkerson}}{\abs{V}^2\cdot\abs{E}} \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} -\sourcecode{graph/dinicScaling.cpp} +\sourcecode{graph/dinitzScaling.cpp} \begin{algorithm}{Min-Cost-Max-Flow} \begin{methods} diff --git a/content/other/other.tex b/content/other/other.tex index 8896962..dce0f3d 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -123,7 +123,7 @@ c'(s',v)&=\sum_{u\in{}V}d(u,v)&c'(v,t')&=\sum_{u\in{}V}d(v,u)\\[-0.5ex] c'(u,v)&=c(u,v)-d(u,v)&c'(t,s)&=x \end{align*} - Löse Fluss auf $G'$ mit \textsc{Dinic's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst). + Löse Fluss auf $G'$ mit \textsc{Dinitz's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst). \item \textbf{\textsc{Johnson}s Reweighting Algorithm:} Initialisiere alle Entfernungen mit \texttt{d[i] = 0}. Berechne mit \textsc{Bellmann-Ford} kürzeste Entfernungen. Falls es einen negativen Zyklus gibt abrrechen. diff --git a/test/graph/dinicScaling.cpp b/test/graph/dinicScaling.cpp deleted file mode 100644 index 967d6b1..0000000 --- a/test/graph/dinicScaling.cpp +++ /dev/null @@ -1,61 +0,0 @@ -#include "../util.h" -namespace dinic { -#include -} - -namespace pushRelabel { -#include -} - -void stress_test() { - ll queries = 0; - for (int tries = 0; tries < 20'000; tries++) { - int n = Random::integer(2, 30); - int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); - - dinic::adj.assign(n, {}); - pushRelabel::adj.assign(n, {}); - - Graph g(n); - g.erdosRenyi(m); - g.forEdges([](int a, int b){ - ll w = Random::integer(1, 1'000'000'000'000ll); - dinic::addEdge(a, b, w); - pushRelabel::addEdge(a, b, w); - }); - - ll got = dinic::maxFlow(0, n - 1); - ll expected = pushRelabel::maxFlow(0, n - 1); - - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; - queries += n; - } - cerr << "tested random queries: " << queries << endl; -} - -constexpr int N = 50000; -constexpr int M = 200000; -void performance_test() { - using namespace dinic; - timer t; - Graph g(N); - g.erdosRenyi(M); - adj.assign(N, {}); - g.forEdges([](int a, int b){ - ll w1 = Random::integer(1, 1'000'000'000'000ll); - ll w2 = Random::integer(1, 1'000'000'000'000ll); - addEdge(a, b, w1); - addEdge(b, a, w2); - }); - - t.start(); - hash_t hash = maxFlow(0, N - 1); - t.stop(); - if (t.time > 2000) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; -} - -int main() { - stress_test(); - performance_test(); -} diff --git a/test/graph/dinitzScaling.cpp b/test/graph/dinitzScaling.cpp new file mode 100644 index 0000000..c06d486 --- /dev/null +++ b/test/graph/dinitzScaling.cpp @@ -0,0 +1,61 @@ +#include "../util.h" +namespace dinitz { +#include +} + +namespace pushRelabel { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); + + dinitz::adj.assign(n, {}); + pushRelabel::adj.assign(n, {}); + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([](int a, int b){ + ll w = Random::integer(1, 1'000'000'000'000ll); + dinitz::addEdge(a, b, w); + pushRelabel::addEdge(a, b, w); + }); + + ll got = dinitz::maxFlow(0, n - 1); + ll expected = pushRelabel::maxFlow(0, n - 1); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 50000; +constexpr int M = 200000; +void performance_test() { + using namespace dinitz; + timer t; + Graph g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + ll w1 = Random::integer(1, 1'000'000'000'000ll); + ll w2 = Random::integer(1, 1'000'000'000'000ll); + addEdge(a, b, w1); + addEdge(b, a, w2); + }); + + t.start(); + hash_t hash = maxFlow(0, N - 1); + t.stop(); + if (t.time > 2000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/graph/pushRelabel.cpp b/test/graph/pushRelabel.cpp index ac3b079..42c2e57 100644 --- a/test/graph/pushRelabel.cpp +++ b/test/graph/pushRelabel.cpp @@ -1,6 +1,6 @@ #include "../util.h" -namespace dinic { -#include +namespace dinitz { +#include } namespace pushRelabel { @@ -13,20 +13,20 @@ void stress_test() { int n = Random::integer(2, 30); int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); - dinic::adj.assign(n, {}); + dinitz::adj.assign(n, {}); pushRelabel::adj.assign(n, {}); Graph g(n); g.erdosRenyi(m); g.forEdges([](int a, int b){ ll w = Random::integer(1, 1'000'000'000'000ll); - dinic::addEdge(a, b, w); + dinitz::addEdge(a, b, w); pushRelabel::addEdge(a, b, w); }); ll got = pushRelabel::maxFlow(0, n - 1); - ll expected = dinic::maxFlow(0, n - 1); - + ll expected = dinitz::maxFlow(0, n - 1); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries += n; } -- cgit v1.2.3