8000 Rewrite article on Strongly Connected Components, and add graph pictures by el-sambal · Pull Request #1307 · cp-algorithms/cp-algorithms · GitHub
[go: up one dir, main page]
Skip to content

Rewrite article on Strongly Connected Components, and add graph pictures #1307

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 37 commits into from
Jul 16, 2024
Merged

Rewrite article on Strongly Connected Components, and add graph pictures #1307

merged 37 commits into from
Jul 16, 2024

Conversation

el-sambal
Copy link
Contributor

This pull request contains a rewrite of the article Strongly Connected Components and Condensation Graph.

What changed:

  • The article now has two tikzpictures (emdedded as svg images) to give a visual representation of strongly connected components and the condensation graph. The LaTeX source is included.
  • Improved English grammar and general text flow throughout the article.
  • Changed the font from e.g. $order$ to order where appropriate. Similarly, changed $tout[v]$ and $tin[v]$ to $t_\text{out}[v]$ and $t_\text{in}[v]$.
  • Merged the two Implementation code blocks into one block. (The second block contained code that should have been in the main function in the first block. Therefore I thought it is cleaner to just put it in a single block.)
  • Added comments to the code.
  • Fixed some other small things:
    • The article mentioned the graphs $g$ and $gr$ even though these were never used.
    • The article did not give a clear definition of $t_\text{out}[v]$ and $t_\text{in}[v]$.
    • The article said that sorting all vertices in $G$ by exit time is equivalent to topologically sorting the vertices of $G$. (This is wrong, because $G$ is not necessarily a DAG.)

For the added tikzpictures, the source code and svg files themselves are in a new directory src/graph/strongly-connected-components-tikzpicture.

Let me know what you think!

el-sambal added 10000 28 commits July 6, 2024 13:17
@el-sambal
rewrite definition of SCC and condensation graph
630fad7
@el-sambal
rewrite proof that G^SCC is DAG
9badcf5
@el-sambal
rewrite up to theorem
7c38cc4
@el-sambal
rewrite theorm
998d66d
@el-sambal
define t_in
d0397ff
@el-sambal
rewrite some things and fix mistake in def. SCC
925a84d
@el-sambal
rewrite 2 cases of proof
2653c39
@el-sambal
rewrite up to **algorithm**
8f4c9e4
@el-sambal
rewrite up to runtime complexity
9a2419e
@el-sambal
rewrite all the way until Implementation section
330ffb6
@el-sambal
rename used to visited
e7d3520
@el-sambal
finish rewriting article
4a1226f
@el-sambal
make something not boldface
bbb4ffb
@el-sambal
remove "nonempty"
cd7bd2f
@el-sambal
subtle (but necessary) rewrite
028e313
@el-sambal
make .tex file for graph
43872c5
@el-sambal
trying out tikz things
dea2c18
@el-sambal
graph looks good
9884016
@el-sambal
graph looks even better
ea7215f
@el-sambal
embed svg into webpage
b28b549
@el-sambal
write SCC(G_example)
248b677
@el-sambal
include condensation graph picture
469c6f4
@el-sambal
change title
b46830c
@el-sambal
final commit (probably) before PR
c144189
@el-sambal
change # into ##
f5a4c9f
@el-sambal
(add sentence about multigraph)
f4b3019
@el-sambal
make code more concise (and fix small mistake)
0e22d2b
@el-sambal
center images
57a5017
@github-actions GitHub Actions
Copy link
Contributor

Visit the preview URL for this PR (for commit 57a5017):

https://cp-algorithms--preview-1307-doz6kdtp.web.app

(expires 2024-07-18T14:32:14.340265812Z)

adamant-pwn
adamant-pwn requested changes Jul 12, 2024
View reviewed changes
Copy link
Member
@adamant-pwn adamant-pwn left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hi, thank you very much, I think it's a significant improvement! Could you please go over review comments before we merge this?

@el-sambal
Copy link
Contributor Author

Thanks for your suggestions!

@github-actions GitHub Actions
Copy link
Contributor

Visit the preview URL for this PR (for commit 9054c35):

https://cp-algorithms--preview-1307-doz6kdtp.web.app

(expires 2024-07-23T00:49:57.826813480Z)

@github-actions GitHub Actions
Copy link
Contributor

Visit the preview URL for this PR (for commit d45b892):

https://cp-algorithms--preview-1307-doz6kdtp.web.app

(expires 2024-07-23T01:09:10.072101203Z)

@github-actions GitHub Actions
Copy link
Contributor

Visit the preview URL for this PR (for commit < 579F a class="commit-link" data-hovercard-type="commit" data-hovercard-url="https://github.com/cp-algorithms/cp-algorithms/commit/15b6f5b2090d1c29d223a827cd74a8a46d3082f7/hovercard" href="https://github.com/cp-algorithms/cp-algorithms/commit/15b6f5b2090d1c29d223a827cd74a8a46d3082f7">15b6f5b):

https://cp-algorithms--preview-1307-doz6kdtp.web.app

(expires 2024-07-23T01:10:37.607076414Z)

adamant-pwn
adamant-pwn approved these changes Jul 16, 2024
View reviewed changes
Copy link
Member
@adamant-pwn adamant-pwn left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks!

@adamant-pwn adamant-pwn merged commit edea689 into cp-algorithms:master Jul 16, 2024
2 checks passed
@adamant-pwn adamant-pwn mentioned this pull request Oct 12, 2024
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@adamant-pwn adamant-pwn adamant-pwn approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@el-sambal @adamant-pwn
0