Merge pull request #1307 from el-sambal/master

adamant-pwn · web-flow · commit edea6890f164 · 2024-07-16T03:32:04.000+02:00
Rewrite article on Strongly Connected Components, and add graph pictures
diff --git a/README.md b/README.md
@@ -16,6 +16,7 @@ Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorith
 
 ## Changelog
 
+- July 16, 2024: Major overhaul of the [Finding strongly connected components / Building condensation graph](https://cp-algorithms.com/graph/strongly-connected-components.html) article.
 - June 26, 2023: Added automatic RSS feeds for [new articles](https://cp-algorithms.com/feed_rss_created.xml) and [updates in articles](https://cp-algorithms.com/feed_rss_updated.xml).
 - December 20, 2022: The repository name and the owning organizations were renamed! Now the repo is located at [https://github.com/cp-algorithms/cp-algorithms](https://github.com/cp-algorithms/cp-algorithms). It is recommended to update the upstream link in your local repositories, if you have any.
 - October 31, 2022: It is now possible to select and copy $\LaTeX$ source code of formulas within the articles.
diff --git a/src/graph/strongly-connected-components-tikzpicture/.gitignore b/src/graph/strongly-connected-components-tikzpicture/.gitignore
@@ -0,0 +1,3 @@
+*.log
+*.aux
+*.pdf
diff --git a/src/graph/strongly-connected-components-tikzpicture/cond_graph.svg b/src/graph/strongly-connected-components-tikzpicture/cond_graph.svg
diff --git a/src/graph/strongly-connected-components-tikzpicture/cond_graph.tex b/src/graph/strongly-connected-components-tikzpicture/cond_graph.tex
@@ -0,0 +1,22 @@
+\documentclass[tikz]{standalone}
+\usepackage{xcolor}
+\usetikzlibrary{arrows,positioning,quotes,backgrounds,arrows.meta,bending,positioning,shapes,shapes.geometric}
+\begin{document}
+\begin{tikzpicture}
+	[scale=2.5,very thick,every node/.style={draw,inner sep=0.18cm,outer sep=1.5mm}, every path/.style={->}]
+
+	%\draw[help lines] (-1,-2) grid (7,2);
+    \node[rectangle,green,fill=green!20] (0) at (0,0) {\color{black}\textbf{\{0,7\}}};
+    \node[rectangle,red,fill=red!20] (1) at (1,0.5) {\color{black}\textbf{\{1,2,3,5,6\}}};
+    \node[rectangle,blue,fill=blue!20] (4) at (2,0) {\color{black}\textbf{\{4,9\}}};
+    \node[rectangle,yellow,fill=yellow!20] (8) at (1,-0.3) {\color{black}\textbf{\{8\}}};
+
+    \path (0) edge (1);
+    \path (0) edge (8);
+    \path (1) edge (4);
+    \path (8) edge (1);
+    \path (8) edge (4);
+
+\end{tikzpicture}
+
+\end{document}
diff --git a/src/graph/strongly-connected-components-tikzpicture/graph.svg b/src/graph/strongly-connected-components-tikzpicture/graph.svg
diff --git a/src/graph/strongly-connected-components-tikzpicture/graph.tex b/src/graph/strongly-connected-components-tikzpicture/graph.tex
@@ -0,0 +1,50 @@
+\documentclass[tikz]{standalone}
+\usepackage{xcolor}
+\usetikzlibrary{arrows,positioning,quotes,backgrounds,arrows.meta,bending,positioning,shapes,shapes.geometric}
+\begin{document}
+\pgfdeclarelayer{background}
+\pgfsetlayers{background,main}
+\begin{tikzpicture}
+	[scale=1.3,very thick,every circle node/.style={draw,inner sep=0.18cm,outer sep=1.1mm,fill=brown!30}, every path/.style={->}]
+
+	%\draw[help lines] (-1,-2) grid (7,2);
+	\node[circle] (0) at (0,0) {\textbf0};
+	\node[circle] (1) at (1,1) {\textbf1};
+	\node[circle] (2) at (3,1) {\textbf2};
+	\node[circle] (3) at (5,1) {\textbf3};
+	\node[circle] (4) at (6,0) {\textbf4};
+	\node[circle] (5) at (4,0) {\textbf5};
+	\node[circle] (6) at (2,0) {\textbf6};
+	\node[circle] (7) at (1,-1) {\textbf7};
+	\node[circle] (8) at (3,-1) {\textbf8};
+	\node[circle] (9) at (5,-1) {\textbf9};
+
+	\path (0) edge (1);
+	\path (0) edge[bend left=20] (7);
+    \path (1) edge[loop below] (1);
+	\path (1) edge[bend left=20] (2);
+	\path (2) edge[bend left=20] (1);
+	\path (2) edge (5);
+	\path (3) edge (2);
+	\path (3) edge (4);
+	\path (4) edge[bend left=20] (9);
+	\path (5) edge (3);
+	\path (5) edge (6);
+	\path (5) edge (9);
+	\path (6) edge (2);
+	\path (7) edge[bend left=20] (0);
+	\path (7) edge (6);
+	\path (7) edge (8);
+	\path (8) edge (6);
+	\path (8) edge (9);
+	\path (9) edge[bend left=20] (4);
+
+	\begin{pgfonlayer}{background}
+		\draw[thick, red, fill=red!20!white] plot [smooth cycle,tension=0.65] coordinates{(0.65,1.3)(4.7,1.52)(5.4,0.7)(4.25,-.4)(3,-.33)(1.5,-.4)};
+		\draw[thick, green, fill=green!20!white] plot [smooth cycle,tension=0.7] coordinates{(0.2,0.4)(1.5,-0.9)(.9,-1.5)(-.45,-.1)};
+		\draw[thick, blue, fill=blue!20!white] plot [smooth cycle,tension=0.7] coordinates{(5.8,0.5)(4.45,-0.8)(5.1,-1.5)(6.6,-.1)};
+		\draw[thick, yellow, fill=yellow!20!white] plot [smooth cycle,tension=0.9] coordinates{(3,-0.5)(3.6,-1)(3,-1.5)(2.4,-1)};
+	\end{pgfonlayer}
+\end{tikzpicture}
+
+\end{document}
diff --git a/src/graph/strongly-connected-components-tikzpicture/info.txt b/src/graph/strongly-connected-components-tikzpicture/info.txt
@@ -0,0 +1,5 @@
+These are the pictures (graphs) used in the article about Strongly Connected Components and the Condensation graph.
+
+Compile the .tex file with pdflatex, and then use a command line tool like pdf2svg to convert the compiled pdf into an svg file. We want svg because it is scalable, i.e. still looks good when the user zooms in far.
+
+This svg can than be directly included in the markdown.
diff --git a/src/graph/strongly-connected-components.md b/src/graph/strongly-connected-components.md
diff --git a/test/test_strongly_connected_components.cpp b/test/test_strongly_connected_components.cpp
@@ -0,0 +1,50 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+#include "strongly_connected_components.h"
+
+int main() {
+    // we only have a single test case for now
+    int n = 10;
+    vector<vector<int>> adj(n);
+    adj[0].push_back(1);
+    adj[0].push_back(7);
+    adj[1].push_back(1);
+    adj[1].push_back(2);
+    adj[2].push_back(1);
+    adj[2].push_back(5);
+    adj[3].push_back(2);
+    adj[3].push_back(4);
+    adj[4].push_back(9);
+    adj[5].push_back(3);
+    adj[5].push_back(6);
+    adj[5].push_back(9);
+    adj[6].push_back(2);
+    adj[7].push_back(0);
+    adj[7].push_back(6);
+    adj[7].push_back(8);
+    adj[8].push_back(6);
+    adj[8].push_back(9);
+    adj[9].push_back(4);
+
+    vector<vector<int>> components, adj_scc;
+    strongy_connected_components(adj, components, adj_scc);
+
+    // sort things to make it easier to verify
+    sort(components.begin(), components.end(),
+         [](auto &l, auto &r) { return l[0] < r[0]; });
+    for (vector<int> a : adj_scc)
+        sort(a.begin(), a.end());
+
+    assert(components.size() == 4);
+    assert(components[0] == std::vector<int>({0, 7}));
+    assert(components[1] == std::vector<int>({1, 2, 3, 5, 6}));
+    assert(components[2] == std::vector<int>({4, 9}));
+    assert(components[3] == std::vector<int>({8}));
+
+    assert(adj_scc[0] == std::vector<int>({1, 1, 8}));
+    assert(adj_scc[1] == std::vector<int>({4, 4}));
+    assert(adj_scc[8] == std::vector<int>({1, 4}));
+
+    return 0;
+}
