Calculator input
Example data table
The sample graph below is the default dataset preloaded into the form.
| Source | Target | Interpretation |
|---|---|---|
| A | B | Part of a three-node mutual cycle |
| B | C | Continues the first cycle |
| C | A | Closes SCC {A, B, C} |
| C | D | Connects first SCC to second SCC |
| D | E | Forms a two-node mutual group |
| E | D | Closes SCC {D, E} |
| E | F | Feeds into a later SCC |
| F | G | Begins a two-node cycle |
| G | F | Closes SCC {F, G} |
| H | H | Creates a cyclic singleton SCC |
Formula used
A strongly connected component is a maximal subset of vertices where every pair of vertices can reach each other through directed paths.
Reachability rule: vertices u and v belong to the same SCC when u ⇢ v and v ⇢ u.
Tarjan low-link method:
- disc[u] = discovery order assigned during depth-first search.
- low[u] = smallest discovery value reachable from u through DFS tree edges and stack-preserving back edges.
low[u] = min( disc[u], disc[v] for back edges, low[w] for DFS children w )
When low[u] = disc[u], vertex u is the root of one complete strongly connected component. The calculator also builds a condensation graph, where each SCC becomes one node and edges connect different components.
How to use this calculator
- Enter a graph name for your report and export files.
- Provide vertex labels, or enter a vertex count and choose 0-based or 1-based indexing.
- Paste one directed edge per line using comma, space, or arrow notation.
- Choose how you want the returned components ordered.
- Press Analyze strongly connected components.
- Review the summary metrics, component table, vertex diagnostics, and Plotly visualization.
- Use the CSV button for structured tabular output and the PDF button for a printable report.
FAQs
1) What is a strongly connected component?
It is a maximal group of vertices in a directed graph where each vertex can reach every other vertex in that same group through directed paths.
2) Which method does this calculator use?
It uses Tarjan’s algorithm. That method tracks discovery order and low-link values during one depth-first traversal to identify SCC roots efficiently.
3) Why are low-link values important?
Low-link values show the earliest discovery index reachable from a vertex while respecting the active DFS stack. Matching discovery and low-link values mark component roots.
4) Does edge direction matter here?
Yes. SCC analysis is defined for directed graphs. Reversing or removing one directed edge can split a previously connected component into smaller groups.
5) Can an isolated vertex be its own SCC?
Yes. Any single vertex forms an SCC by itself. It becomes a cyclic singleton only when it also has a self-loop.
6) What does the condensation graph mean?
The condensation graph collapses every SCC into one node. The resulting graph is always acyclic, which helps you study high-level dependency flow between components.
7) How are duplicate or invalid edges handled?
Duplicate edges are ignored to avoid double counting. Invalid lines are skipped, and the calculator reports them in the notes section after analysis.
8) When is the whole graph strongly connected?
The whole graph is strongly connected when the algorithm finds exactly one SCC containing all vertices, meaning every vertex can reach every other vertex.