diff options
| -rw-r--r-- | content/geometry/polygon.cpp | 2 | ||||
| -rw-r--r-- | content/graph/2sat.cpp | 4 | ||||
| -rw-r--r-- | content/graph/bellmannFord.cpp | 1 | ||||
| -rw-r--r-- | content/graph/graph.tex | 208 | ||||
| -rw-r--r-- | test/graph/2sat.cpp | 3 | ||||
| -rw-r--r-- | test/graph/2sat.cpp.awk | 6 |
6 files changed, 119 insertions, 105 deletions
diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp index 474ce88..ee45539 100644 --- a/content/geometry/polygon.cpp +++ b/content/geometry/polygon.cpp @@ -23,7 +23,7 @@ ll windingNumber(pt p, const vector<pt>& poly) { return res; } -// check if point is inside polygon (any polygon) +// check if p is inside poly (any polygon poly[0] == poly.back()) bool inside(pt p, const vector<pt>& poly) { bool in = false; for (int i = 0; i + 1 < ssize(poly); i++) { diff --git a/content/graph/2sat.cpp b/content/graph/2sat.cpp index 2b49fc6..b9cfd1c 100644 --- a/content/graph/2sat.cpp +++ b/content/graph/2sat.cpp @@ -1,11 +1,9 @@ +constexpr int var(int i) {return i << 1;} // use this! struct sat2 { int n; // + scc variablen vector<int> sol; - sat2(int vars) : n(vars*2), adj(n) {} - static int var(int i) { return i << 1; } // use this! - void addImpl(int a, int b) { adj[a].push_back(b); adj[1^b].push_back(1^a); diff --git a/content/graph/bellmannFord.cpp b/content/graph/bellmannFord.cpp index 09ea1aa..cadcde7 100644 --- a/content/graph/bellmannFord.cpp +++ b/content/graph/bellmannFord.cpp @@ -9,7 +9,6 @@ auto bellmannFord(int n, vector<edge>& edges, int start) { dist[e.to] = dist[e.from] + e.cost; prev[e.to] = e.from; }}} - for (edge& e : edges) { if (dist[e.from] != INF && dist[e.from] + e.cost < dist[e.to]) { diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 7763d79..e46ad07 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -76,15 +76,42 @@ \sourcecode{graph/treeIsomorphism.cpp} \end{algorithm} -\subsection{Kürzeste Wege} +\begin{algorithm}{DFS} + \input{graph/dfs} +\end{algorithm} -\subsubsection{\textsc{Bellmann-Ford}-Algorithmus} -\method{bellmanFord}{kürzeste Pfade oder negative Kreise finden}{\abs{V}\*\abs{E}} -\sourcecode{graph/bellmannFord.cpp} +\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} + \begin{methods} + \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} + \end{methods} + \textbf{Info:} SCCs sind in umgekehrter topologischer Reihenfolge! + \sourcecode{graph/scc.cpp} +\end{algorithm} -\subsubsection{Algorithmus von \textsc{Dijkstra}} -\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})} -\sourcecode{graph/dijkstra.cpp} +\begin{algorithm}{2-SAT} + \sourcecode{graph/2sat.cpp} +\end{algorithm} + +\begin{algorithm}{Artikulationspunkte, Brücken und BCC} + \begin{methods} + \method{find}{berechnet Artikulationspunkte, Brücken und BCC}{\abs{V}+\abs{E}} + \end{methods} + \textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC. + \sourcecode{graph/articulationPoints.cpp} +\end{algorithm} + +\begin{algorithm}{Cycle Counting} + \begin{methods} + \method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}} + \method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}} + \end{methods} + \begin{itemize} + \item jeder Zyklus ist das xor von einträgen in \code{base}. + \end{itemize} + \sourcecode{graph/cycleCounting.cpp} +\end{algorithm} + +\subsection{Kürzeste Wege} \subsubsection{\textsc{Floyd-Warshall}-Algorithmus} \method{floydWarshall}{kürzeste Pfade oder negative Kreise finden}{\abs{V}^3} @@ -100,6 +127,14 @@ Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} \cdot b_{k\smash{j}}$ +\subsubsection{\textsc{Bellmann-Ford}-Algorithmus} +\method{bellmanFord}{kürzeste Pfade oder negative Kreise finden}{\abs{V}\*\abs{E}} +\sourcecode{graph/bellmannFord.cpp} + +\subsubsection{Algorithmus von \textsc{Dijkstra}} +\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})} +\sourcecode{graph/dijkstra.cpp} + \begin{algorithm}{Dynamic Connectivity} \begin{methods} \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m} @@ -108,39 +143,14 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/connect.cpp} \end{algorithm} +\clearpage + + -\begin{algorithm}{\textsc{Erd\H{o}s-Gallai}} - Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$ - \begin{methods} - \method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})} - \end{methods} - \sourcecode{graph/havelHakimi.cpp} -\end{algorithm} -\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} - \begin{methods} - \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} - \end{methods} - SCCs sind in umgekehrter topologischer Reihenfolge! - \sourcecode{graph/scc.cpp} -\end{algorithm} -\begin{algorithm}{DFS} - \input{graph/dfs} -\end{algorithm} -\begin{algorithm}{Artikulationspunkte, Brücken und BCC} - \begin{methods} - \method{find}{berechnet Artikulationspunkte, Brücken und BCC}{\abs{V}+\abs{E}} - \end{methods} - \textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC. - \sourcecode{graph/articulationPoints.cpp} -\end{algorithm} -\vfill\null\columnbreak -\begin{algorithm}{2-SAT} - \sourcecode{graph/2sat.cpp} -\end{algorithm} \begin{algorithm}{Maximal Cliques} \begin{methods} @@ -150,17 +160,35 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/bronKerbosch.cpp} \end{algorithm} -\begin{algorithm}{Cycle Counting} +\begin{algorithm}{Maximum Cardinality Bipartite Matching} + \label{kuhn} \begin{methods} - \method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}} - \method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}} + \method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})} \end{methods} \begin{itemize} - \item jeder Zyklus ist das xor von einträgen in \code{base}. + \item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen \end{itemize} - \sourcecode{graph/cycleCounting.cpp} + \sourcecode{graph/kuhn.cpp} + \columnbreak + \begin{methods} + \method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}} + \end{methods} + \sourcecode{graph/hopcroftKarp.cpp} +\end{algorithm} + +\vfill\null +\columnbreak + +\begin{algorithm}{Maximum Weight Bipartite Matching} + \begin{methods} + \method{match}{berechnet Matching}{\abs{V}^3} + \end{methods} + \sourcecode{graph/maxWeightBipartiteMatching.cpp} \end{algorithm} +\vfill\null +\columnbreak + \begin{algorithm}{Wert des maximalen Matchings} Fehlerwahrscheinlichkeit: $\left(\frac{m}{MOD}\right)^I$ \sourcecode{graph/matching.cpp} @@ -173,28 +201,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/blossom.cpp} \end{algorithm} -\begin{algorithm}{Rerooting Template} - \sourcecode{graph/reroot.cpp} -\end{algorithm} - -\begin{algorithm}{Virtual Trees} - \sourcecode{graph/virtualTree.cpp} -\end{algorithm} - -\begin{algorithm}{Maximum Cardinality Bipartite Matching} - \label{kuhn} - \begin{methods} - \method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})} - \end{methods} - \begin{itemize} - \item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen - \end{itemize} - \sourcecode{graph/kuhn.cpp} - \begin{methods} - \method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}} - \end{methods} - \sourcecode{graph/hopcroftKarp.cpp} -\end{algorithm} +\vfill\null +\columnbreak \begin{algorithm}{Global Mincut} \begin{methods} @@ -205,15 +213,31 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/stoerWagner.cpp} \end{algorithm} +\begin{algorithm}{Rerooting Template} + \sourcecode{graph/reroot.cpp} +\end{algorithm} + +\begin{algorithm}{Virtual Trees} + \sourcecode{graph/virtualTree.cpp} +\end{algorithm} + +\begin{algorithm}{\textsc{Erd\H{o}s-Gallai}} + Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$ + \begin{methods} + \method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})} + \end{methods} + \sourcecode{graph/havelHakimi.cpp} +\end{algorithm} + \subsection{Max-Flow} \optional{ -\subsubsection{Push Relabel \opthint} -\begin{methods} - \method{maxFlow}{gut bei sehr dicht besetzten Graphen.}{\abs{V}^2\*\sqrt{\abs{E}}} - \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} -\end{methods} -\sourcecode{graph/pushRelabel.cpp} + \subsubsection{Push Relabel \opthint} + \begin{methods} + \method{maxFlow}{gut bei sehr dicht besetzten Graphen.}{\abs{V}^2\*\sqrt{\abs{E}}} + \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} + \end{methods} + \sourcecode{graph/pushRelabel.cpp} } \subsubsection{\textsc{Dinitz}'s Algorithm mit Capacity Scaling} @@ -232,37 +256,27 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \columnbreak \optional{ -\subsubsection{Anwendungen \opthint} -\begin{itemize} - \item \textbf{Maximum Edge Disjoint Paths}\newline - Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. - \begin{enumerate} - \item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante auf 1. - \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Kanten. - \end{enumerate} - \item \textbf{Maximum Independent Paths}\newline - Finde die maximale Anzahl an Pfaden von $s$ nach $t$, die keinen Knoten teilen. - \begin{enumerate} - \item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante \emph{und jedes Knotens} auf 1. - \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Knoten. - \end{enumerate} - \item \textbf{Min-Cut}\newline - Der maximale Fluss ist gleich dem minimalen Schnitt. - Bei Quelle $s$ und Senke $t$, partitioniere in $S$ und $T$. - Zu $S$ gehören alle Knoten, die im Residualgraphen von $s$ aus erreichbar sind (Rückwärtskanten beachten). -\end{itemize} + \subsubsection{Anwendungen} + \begin{itemize} + \item \textbf{Maximum Edge Disjoint Paths}\newline + Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. + \begin{enumerate} + \item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante auf 1. + \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Kanten. + \end{enumerate} + \item \textbf{Maximum Independent Paths}\newline + Finde die maximale Anzahl an Pfaden von $s$ nach $t$, die keinen Knoten teilen. + \begin{enumerate} + \item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante \emph{und jedes Knotens} auf 1. + \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Knoten. + \end{enumerate} + \item \textbf{Min-Cut}\newline + Der maximale Fluss ist gleich dem minimalen Schnitt. + Bei Quelle $s$ und Senke $t$, partitioniere in $S$ und $T$. + Zu $S$ gehören alle Knoten, die im Residualgraphen von $s$ aus erreichbar sind (Rückwärtskanten beachten). + \end{itemize} } -\begin{algorithm}{Maximum Weight Bipartite Matching} - \begin{methods} - \method{match}{berechnet Matching}{\abs{V}^3} - \end{methods} - \sourcecode{graph/maxWeightBipartiteMatching.cpp} -\end{algorithm} -\vfill\null -\columnbreak - - \begin{algorithm}[optional]{TSP} \begin{methods} \method{TSP}{berechnet eine Tour}{n^2\*2^n} diff --git a/test/graph/2sat.cpp b/test/graph/2sat.cpp index fc3186e..cf37131 100644 --- a/test/graph/2sat.cpp +++ b/test/graph/2sat.cpp @@ -1,9 +1,6 @@ #include "../util.h" #include <graph/scc.cpp> -#define static vector<vector<int>> adj; static // hacky... #include <graph/2sat.cpp> -#undef static -#undef adj struct RandomClause { int a, b; diff --git a/test/graph/2sat.cpp.awk b/test/graph/2sat.cpp.awk new file mode 100644 index 0000000..d0215d8 --- /dev/null +++ b/test/graph/2sat.cpp.awk @@ -0,0 +1,6 @@ +/scc variablen/ { + print; + print "\tvector<vector<int>> adj;"; + next +} +{ print } |