-
Notifications
You must be signed in to change notification settings - Fork 1
Cuts
James Bremner edited this page Dec 17, 2023
·
2 revisions
This option finds the Cut Vertices ( AKA Articulation Points ) in an undirected graph. These are the vertices that, if any one is removed, then the graph is split into an increased number of unconnected components.
The first line specifies the calculation required. It must contain
format cuts
| Column | Description |
|---|---|
| 1 | l for link |
| 2 | node name |
| 3 | node name |
Finds cut vertices using the Tarjan algorithm. https://en.wikipedia.org/wiki/Biconnected_component
This code can handle, without exhausting the default stack size, a graph with 4,720 vertices 13,722 edges from https://dyngraphlab.github.io/ ( 3elt.graph.seq.txt ) in 27 seconds.