Strongly Connected Components (Variant 16)

Simple Python solution for the assignment:

• find SCCs in a directed graph (Kosaraju),
• build the condensation DAG,
• output one topological ordering of that DAG,
• optional verification with networkx.

Why this works (quick theory)

• SCC: maximal set of vertices where every vertex reaches every other.
• Kosaraju runs two DFS passes: (1) DFS on the original graph to record vertices by finish time; (2) DFS on the reversed graph in that order to peel off SCCs. Each vertex is visited O(1) times -> total O(V+E).
• Condensation graph collapses each SCC to a node; between two components we keep a single directed edge if any original edge crosses them. This graph is always a DAG.
• Topological sort (Kahn) repeatedly removes zero-indegree nodes from the DAG; succeeds iff the graph is acyclic.

Input format

N
u v
u v
...

• N - vertex count.
• Each following line is a directed edge u v.
• Vertices may be 1-based (as in samples) or 0-based; internally converted to 0-based.
• Lines starting with # are ignored (in case of comments).

Usage

From the repository root:

python -m src.main --input sample_data/graph1.txt
python -m src.main --input sample_data/graph2.txt --verify  # tries networkx if installed

On Windows cmd:

python -m src.main --input sample_data\graph1.txt

Optional verification:

pip install networkx
python -m src.main --input sample_data\graph1.txt --verify

Complexity

• Kosaraju: O(V+E) time, O(V+E) memory.
• Condensation build: O(E) time, O(V) memory for the map.
• Topological sort: O(V+E) for the DAG (here V = number of components).

Topological sorting

We use Kahn's algorithm:

1. Compute indegree of each DAG node.
2. Push all zero-indegree nodes into a queue.
3. Repeatedly pop from the queue, append to ordering, decrement indegrees of outgoing neighbors, and enqueue new zeros. If all nodes are emitted, the graph was a DAG; otherwise a cycle existed (should not happen here). Complexity O(V+E) on the condensation graph.

Implementation overview (Python, standard library only)

• src/scc_kosaraju.py - iterative Kosaraju SCC.
• src/condensation.py - builds condensation DAG edges.
• src/topo_sort.py - Kahn topological sort.
• src/graph_io.py - small text parser (supports 1-based input).
• src/main.py - CLI: loads a graph, prints SCCs, condensation edges, topological order, optional networkx check.