What graph input formats are accepted?

You can provide edge lists (such as 'a -> b' or 'a b') or adjacency lists (such as 'a: b c'), with one record per line.

How are Tarjan's and Kosaraju's algorithms cross-checked?

Tarjan's iterative stack-based algorithm and Kosaraju's two-pass finish-time algorithm run independently and must yield matching components for verification.

How are bridges and articulation points determined?

They are identified on the undirected graph view using low-link and discovery times: low[v] > disc[u] marks a bridge, and low[v] >= disc[u] (or a root with multiple children) marks an articulation point.

Can the tool perform a full topological sort on graphs with cycles?

A full topological sort is only valid on acyclic graphs, but the tool will always produce a valid Kahn topological order on the condensed DAG of components.

What does the maximum depth setting control?

It restricts the layer depth reached during breadth-first search (BFS) and explicit-stack depth-first search (DFS) traversals starting from the specified start node.

Elysia Tools

Navigation

Development

Tarjan SCC / Bridge / Articulation-Point Graph Decomposer with Condensation Topological Order

Decompose a directed or undirected graph with Tarjan's 1972 iterative SCC algorithm cross-checked against Kosaraju's two-pass; find articulation points and bridges via low-links; build the condensation DAG with a Kahn topological order; report cycles (nodes on cycles, self-loops) and depth-limited BFS/DFS traversals.

Details

What this tool helps you do

Tarjan's SCC runs iteratively with an explicit stack (disc/low arrays, components collected on pop); Kosaraju orders vertices by iterative finish time then collects on the reversed graph — both must agree component-for-component (mutual verification). Bridges and articulation points use low-links on the undirected view: low[v] > disc[u] means a bridge; a root with ≥2 subtree children or low[v] ≥ disc[u] means an articulation point. The condensation builds a DAG over components ordered by Kahn's in-degree method; the original graph admits a full topological order iff acyclic (nodes on cycles counted as SCCs of size > 1 plus self-loops). BFS proceeds layer by layer, DFS with an explicit stack; both honor the depth limit. All passes are O(V+E).

Execution

Run this tool

Fill in the form, run the tool, and review the result in one place.

Samples

Tarjan SCC / Bridge / Articulation-Point Graph Decomposer with Condensation Topological Order

What this tool helps you do

Run this tool

Examples that match this tool

Continue with connected tools and hubs

Learn when to use this tool, what it supports, and how real users apply it.

Key facts

Overview

When to use

How it works

Use cases

Examples

1. Cyclic Dependency Decomposition in Microservices

2. Network Reliability and Bridge Detection

FAQ

Copyright-Free FLAC Audio Samples

Copyright-Free WAV Audio Samples

Android Image Processing Java Samples

Android Image Processing Kotlin Samples

Cron Expression Visualizer

Tailwind Color Palette Sync

Cron Expression Explainer

Cron Job Simulator