diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/2sat.cpp | 22 | ||||
| -rw-r--r-- | graph/articulationPoints.cpp | 2 | ||||
| -rw-r--r-- | graph/cycleCounting.cpp | 27 | ||||
| -rw-r--r-- | graph/euler.cpp | 11 | ||||
| -rw-r--r-- | graph/graph.tex | 110 |
5 files changed, 84 insertions, 88 deletions
diff --git a/graph/2sat.cpp b/graph/2sat.cpp index 2ebb11a..4e47ba0 100644 --- a/graph/2sat.cpp +++ b/graph/2sat.cpp @@ -4,19 +4,19 @@ struct sat2 { sat2(int vars) : n(vars*2), adjlist(vars*2) {}; - static int var(int i) {return i << 1;} + static int var(int i) {return i << 1;} // use this! - void addImpl(int v1, int v2) { - adjlist[v1].push_back(v2); - adjlist[1^v2].push_back(1^v1); + void addImpl(int a, int b) { + adjlist[a].push_back(b); + adjlist[1^b].push_back(1^a); } - void addEquiv(int v1, int v2) {addImpl(v1, v2); addImpl(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);} - void addAnd(int v1, int v2) {addTrue(v1); addTrue(v2);} - void addNand(int v1, int v2) {addOr(1^v1, 1^v2);} + void addEquiv(int a, int b) {addImpl(a, b); addImpl(b, a);} + void addOr(int a, int b) {addImpl(1^a, b);} + void addXor(int a, int b) {addOr(a, b); addOr(1^a, 1^b);} + void addTrue(int a) {addImpl(1^a, a);} + void addFalse(int a) {addTrue(1^a);} + void addAnd(int a, int b) {addTrue(a); addTrue(b);} + void addNand(int a, int b) {addOr(1^a, 1^b);} bool solvable() { scc(); //scc code von oben diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp index 0df1eeb..fb18d36 100644 --- a/graph/articulationPoints.cpp +++ b/graph/articulationPoints.cpp @@ -29,7 +29,7 @@ int dfs(int v, int parent = -1) { return top; } -void findArticulationPoints() { +void find() { counter = 0; num.assign(sz(adjlist), 0); isArt.assign(sz(adjlist), false); diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp index b64b230..c3fe457 100644 --- a/graph/cycleCounting.cpp +++ b/graph/cycleCounting.cpp @@ -1,15 +1,14 @@ -constexpr ll maxEdges = 128; +constexpr int maxEdges = 128; using cycle = bitset<maxEdges>; struct cylces { - ll n; - vector<vector<pair<ll, ll>>> adj; + vector<vector<pair<int, int>>> adj; vector<bool> seen; vector<cycle> paths, base; - vector<pair<ll, ll>> edges; + vector<pair<int, int>> edges; - cylces(ll n) : n(n), adj(n), seen(n), paths(n) {} + cylces(int n) : adj(n), seen(n), paths(n) {} - void addEdge(ll a, ll b) { + void addEdge(int a, int b) { adj[a].push_back({b, sz(edges)}); adj[b].push_back({a, sz(edges)}); edges.push_back({a, b}); @@ -23,8 +22,8 @@ struct cylces { if (cur.any()) base.push_back(cur); } - void findBase(ll c = 0, ll p = -1, cycle cur = {}) { - if (n == 0) return; + void findBase(int c = 0, int p = -1, cycle cur = {}) { + if (adj.empty()) return; if (seen[c]) { addBase(cur ^ paths[c]); } else { @@ -40,8 +39,8 @@ struct cylces { //cycle must be constrcuted from base bool isCycle(cycle cur) { if (cur.none()) return false; - init(n); - for (ll i = 0; i < sz(edges); i++) { + init(sz(adj)); // union find + for (int i = 0; i < sz(edges); i++) { if (cur[i]) { cur[i] = false; if (findSet(edges[i].first) == @@ -51,12 +50,12 @@ struct cylces { return cur.none(); }; - ll count() { + int count() { findBase(); - ll res = 0; - for (ll i = 1; i < (1ll << sz(base)); i++) { + int res = 0; + for (int i = 1; i < (1 << sz(base)); i++) { cycle cur; - for (ll j = 0; j < sz(base); j++) { + for (int j = 0; j < sz(base); j++) { if (((i >> j) & 1) != 0) cur ^= base[j]; if (isCycle(cur)) res++; } diff --git a/graph/euler.cpp b/graph/euler.cpp index 0907ab2..6ef3c13 100644 --- a/graph/euler.cpp +++ b/graph/euler.cpp @@ -6,21 +6,18 @@ void addEdge(int a, int b) { idx[a].push_back(sz(to)); to.push_back(b); used.push_back(false); - idx[b].push_back(sz(to)); //für ungerichtet + idx[b].push_back(sz(to)); // für ungerichtet to.push_back(a); used.push_back(false); } -// Findet Eulerzyklus an Knoten n startend. -// init idx und validIdx -void euler(int n) { +void euler(int n) { // init idx und validIdx for (;validIdx[n] < sz(idx[n]); validIdx[n]++) { if (!used[idx[n][validIdx[n]]]) { int nn = to[idx[n][validIdx[n]]]; used[idx[n][validIdx[n]]] = true; - used[idx[n][validIdx[n]] ^ 1] = true; //für ungerichtet + used[idx[n][validIdx[n]] ^ 1] = true; // für ungerichtet euler(nn); }} - // Zyklus in cycle in umgekehrter Reihenfolge. - cycle.push_back(n); + cycle.push_back(n); // Zyklus in umgekehrter Reihenfolge. } diff --git a/graph/graph.tex b/graph/graph.tex index a26661d..47f1d75 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -68,52 +68,6 @@ Sei $d_{ij}$ die Distanzmatrix von $G$, dann gibt $d_{ij}^k$ die kürzeste Dista Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{ij}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{ij} = a_{ij} \* b_{ij} = \sum a_{ik} + b_{kj}$ -\begin{algorithm}{Artikulationspunkte, Brücken und BCC} - \begin{methods} - \method{findArticulationPoints}{berechnet Artikulationspunkte,}{\abs{V}+\abs{E}} - \method{}{Brücken und BCC}{} - \end{methods} - \textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC. - \sourcecode{graph/articulationPoints.cpp} -\end{algorithm} - -\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} - \begin{methods} - \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} - \end{methods} - \sourcecode{graph/scc.cpp} -\end{algorithm} - -\begin{algorithm}{2-SAT} - \sourcecode{graph/2sat.cpp} -\end{algorithm} - -\begin{algorithm}{Eulertouren} - \begin{methods} - \method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}} - \end{methods} - \sourcecode{graph/euler.cpp} - \begin{itemize} - \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). - \item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). - \item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.} - \item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adjlist} leichter - \item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert. - Die Existenz muss separat geprüft werden. - \end{itemize} -\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} - \begin{algorithm}{Lowest Common Ancestor} \begin{methods} \method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})} @@ -132,14 +86,33 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da Subbaum unter dem Knoten $v$ ist das Intervall $[\text{\code{in[v]}},~\text{\code{out[v]}})$. \sourcecode{graph/hld.cpp} \end{algorithm} +\clearpage -\begin{algorithm}{Dynamic Connectivity} +\begin{algorithm}{Maximal Cliques} \begin{methods} - \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m} - \method{addEdge}{fügt Kannte ein,\texttt{id}=delete Zeitpunkt}{\log(n)} - \method{eraseEdge}{entfernt Kante \texttt{id}}{\log(n)} + \method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}} + \method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1} \end{methods} - \sourcecode{graph/connect.cpp} + \sourcecode{graph/bronKerbosch.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}{Strongly Connected Components (\textsc{Tarjan})} + \begin{methods} + \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} + \end{methods} + \sourcecode{graph/scc.cpp} +\end{algorithm} + +\begin{algorithm}{2-SAT} + \sourcecode{graph/2sat.cpp} \end{algorithm} \begin{algorithm}{Global Mincut} @@ -254,10 +227,37 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{algorithm} } -\begin{algorithm}{Maximal Cliques} +\begin{algorithm}{Cycle Counting} \begin{methods} - \method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}} - \method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1} + \method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}} + \method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}} \end{methods} - \sourcecode{graph/bronKerbosch.cpp} + \begin{itemize} + \item jeder Zyklus ist das xor von einträgen in \code{base}. + \end{itemize} + \sourcecode{graph/cycleCounting.cpp} +\end{algorithm} + +\begin{algorithm}{Eulertouren} + \begin{methods} + \method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}} + \end{methods} + \sourcecode{graph/euler.cpp} + \begin{itemize} + \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). + \item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). + \item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.} + \item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adjlist} leichter + \item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert. + Die Existenz muss separat geprüft werden. + \end{itemize} +\end{algorithm} + +\begin{algorithm}{Dynamic Connectivity} + \begin{methods} + \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m} + \method{addEdge}{fügt Kannte ein,\texttt{id}=delete Zeitpunkt}{\log(n)} + \method{eraseEdge}{entfernt Kante \texttt{id}}{\log(n)} + \end{methods} + \sourcecode{graph/connect.cpp} \end{algorithm} |