`condensation`

Condensation of a digraph: each strongly connected component becomes one node.

Category: Mathematics > Graph and Network Algorithms

Syntax

C = condensation(G)

Returns the condensed digraph.

Description

Two nodes are in the same strongly connected component when each can reach the other. Collapsing every such component into a single node removes all cycles, so the result is always a directed acyclic graph. That makes condensation useful before an ordering or scheduling step.

Component membership of each original node comes from conncomp(G, 'Type', 'strong').

Input arguments

G: A digraph.

Output arguments

C: A digraph with one node per strongly connected component of G, and an edge between two components when G has an edge from one to the other.

Example

Collapsing a cycle

D = digraph([1 2 3 3 4], [2 3 1 4 5]);
C = condensation(D);
fprintf('%d nodes, %d edges, dag: %d\n', numnodes(C), numedges(C), isdag(C))

Output

3 nodes, 2 edges, dag: 1

condensation