Strongly Connected Components Generator
In a directed graph, two nodes belong together when each can reach the other — and that relation carves the graph into strongly connected components. Kosaraju's algorithm finds them with two passes and a reversed graph, which is elegant and completely opaque the first time you see it. This page checks the result against the definition instead: reachability is computed from every node, and the resulting partition must match exactly.
What this generator does
Builds a directed graph seeded with at least one guaranteed cycle, then partitions it with Kosaraju's two-pass algorithm. The partition is verified by computing, for every ordered pair of nodes, whether each reaches the other, and confirming that mutual reachability agrees with the grouping in both directions.
How to use this tool
- Choose a node count and how densely to add directed edges.
- Follow the arrows and look for groups where you can get from any node back to any other.
- Generate, and compare your grouping with the components shown.
- Raise the density until the whole graph collapses into one component.
Understanding the controls
- How many nodes
- Between 4 and 12. The verification is quadratic in nodes and stays instant across the range.
- Extra edge density (%)
- How likely each ordered pair gets an edge. Low values leave many single-node components; high values merge everything into one.
- Seed
- Any word reproduces the same directed graph and the same components.
Common use cases
- Teaching Kosaraju or Tarjan with a partition that has been independently verified
- Worked examples of cyclic dependencies in a module graph
- Test instances for a component-finding implementation
- Showing that a single node with no return path is its own component
- Setting the same directed graph twice from a seed
How this generator works
Kosaraju runs a depth-first search recording the order nodes finish in, then searches the reversed graph in reverse finishing order; each tree of that second pass is one component. Both passes are iterative so a long chain cannot overflow the stack. The check ignores all of that and works from the definition: it runs reachability from every node and confirms that two nodes share a component precisely when each reaches the other.
Randomness and fairness
The graph is random; the components are computed and then proved. Seeded graphs reproduce exactly and are therefore explicitly not cryptographically secure. Without a seed the browser's cryptographically secure generator is used.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- The generator always plants at least one cycle, so a graph of all singletons is rare.
- Components are shown as groups rather than as the condensed acyclic graph they form.
- Twelve nodes is the ceiling, set by the quadratic verification.
- Edges are unweighted — strong connectivity is a reachability question.
- A graph vanishes with the tab; only the seed reproduces it.
Privacy and your data
The directed graph and its components are worked out in your browser alone. Neither the graph nor your seed is transmitted or stored.
Related generators
- Topological Order GeneratorDependency graphs with a valid task order, every edge checked to point forwards and the number of alternative orders counted exactly.
- Graph Traversal GeneratorThe same graph visited breadth-first and depth-first side by side, with the hop count each node sits at.
- Random Graph GeneratorRandom graphs at a density you choose, drawn and exported as an edge list or DOT, with connectivity measured rather than assumed.
- Articulation Point GeneratorConnected graphs with their cut vertices found by depth-first search and confirmed by actually removing each node and counting the pieces.