From 9fe234e7181b1cad9652655e674e7f9f821814b7 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 12:50:19 +0100 Subject: Artikulationpunkte --- graph/graph.tex | 3 +++ 1 file changed, 3 insertions(+) (limited to 'graph/graph.tex') diff --git a/graph/graph.tex b/graph/graph.tex index 2bf395c..5fc725e 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -13,5 +13,8 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} +\subsection{Artikulationspunkte und Brücken} +\lstinputlisting{graph/articulationPoints.cpp} + \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file -- cgit v1.2.3 From 0bdabf851fd4a83e57fced5864aa85af7029ad48 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 16:59:45 +0100 Subject: Dokument gebaut --- graph/graph.tex | 7 +++++++ tcr.pdf | Bin 306669 -> 313827 bytes tcr.tex | 1 + 3 files changed, 8 insertions(+) (limited to 'graph/graph.tex') diff --git a/graph/graph.tex b/graph/graph.tex index 5fc725e..5982e5a 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -16,5 +16,12 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \subsection{Artikulationspunkte und Brücken} \lstinputlisting{graph/articulationPoints.cpp} +\subsection{Eulertouren} +\begin{itemize} + \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). + \item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). + \item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.} +\end{itemize} + \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index 345a1a7..eec39ab 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 4328b73..3e6a0ed 100644 --- a/tcr.tex +++ b/tcr.tex @@ -8,6 +8,7 @@ \usepackage{amssymb} \usepackage{enumitem} +\setlist{nosep} \usepackage{color} \definecolor{darkred}{rgb}{0.72,0.07,0.07} -- cgit v1.2.3 From 4663f02b5df9713ce2d75b4f19bc6ca103f2d0ce Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 17:10:04 +0100 Subject: eulerzyklen --- graph/euler.cpp | 41 +++++++++++++++++++++++++++++++++++++++++ graph/graph.tex | 2 ++ tcr.pdf | Bin 313827 -> 313603 bytes tcr.tex | 7 ++++++- 4 files changed, 49 insertions(+), 1 deletion(-) create mode 100644 graph/euler.cpp (limited to 'graph/graph.tex') diff --git a/graph/euler.cpp b/graph/euler.cpp new file mode 100644 index 0000000..74b3399 --- /dev/null +++ b/graph/euler.cpp @@ -0,0 +1,41 @@ +vector< vector > adjlist; +vector< vector > otherIdx; +vector cycle; +vector validIdx; + +void swapEdges(int n, int a, int b) { // Vertauscht Kanten mit Indizes a und b von Knoten n. + int neighA = adjlist[n][a]; + int neighB = adjlist[n][b]; + int idxNeighA = otherIdx[n][a]; + int idxNeighB = otherIdx[n][b]; + swap(adjlist[n][a], adjlist[n][b]); + swap(otherIdx[n][a], otherIdx[n][b]); + otherIdx[neighA][idxNeighA] = b; + otherIdx[neighB][idxNeighB] = a; +} + +void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehoerige Rueckwaertskante). + int other = adjlist[n][i]; + if (other == n) { //Schlingen + validIdx[n]++; + return; + } + int otherIndex = otherIdx[n][i]; + validIdx[n]++; + if (otherIndex != validIdx[other]) { + swapEdges(other, otherIndex, validIdx[other]); + } + validIdx[other]++; +} + +//findet Eulerzyklus an Knoten n startend +//teste vorher, dass Graph zusammenhaengend ist! (isolierte Punkte sind ok) +//teste vorher, ob Eulerzyklus ueberhaupt existiert! +void euler(int n) { + while (validIdx[n] < (int)adjlist[n].size()) { + int nn = adjlist[n][validIdx[n]]; + removeEdge(n, validIdx[n]); + euler(nn); + } + cycle.push_back(n); //Zyklus am Ende in cycle +} \ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 5982e5a..fada803 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -21,7 +21,9 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). \item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). \item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.} + \item Der Code unten läuft in Linearzeit. Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher. \end{itemize} +\lstinputlisting{graph/euler.cpp} \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index eec39ab..c735878 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 3e6a0ed..cea7d08 100644 --- a/tcr.tex +++ b/tcr.tex @@ -44,13 +44,18 @@ \usepackage[top=2cm, bottom=2cm, left=2cm, right=1cm]{geometry} +\usepackage{multicol} + \title{Team Contest Reference} \author{ChaosKITs \\ Karlsruhe Institute of Technology} \begin{document} \maketitle -\tableofcontents +\setlength{\columnsep}{1cm} +\begin{multicols}{2} + \tableofcontents +\end{multicols} \newpage \input{datastructures/datastructures} -- cgit v1.2.3 From 3e14dcd6c67c80b4cbc5c7e949a25fe20dc676e2 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 20:12:51 +0100 Subject: Update graph.tex --- graph/graph.tex | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'graph/graph.tex') diff --git a/graph/graph.tex b/graph/graph.tex index fada803..b35adc4 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,5 +1,8 @@ \section{Graphen} +\subsection{Lowest Common Ancestor} +\lstinputlisting{graph/LCA.cpp} + \subsection{Kürzeste Wege} \subsubsection{Algorithmus von \textsc{Dijkstra}} @@ -26,4 +29,4 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \lstinputlisting{graph/euler.cpp} \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} -\lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file +\lstinputlisting{graph/edmondsKarp.cpp} -- cgit v1.2.3