`transclosure`

Transitive closure of a directed graph.

Category: Mathematics > Graph and Network Algorithms

Syntax

T = transclosure(G)

Returns a digraph with an edge from u to v whenever v is reachable from u in G.

Description

The transitive closure answers reachability questions directly: if there is a path of any length from node u to node v, the closure has the single edge u -> v. Edges already in G are kept.

In terms of the adjacency matrix, the closure is the pattern of nonzeros of the sum of its powers up to the number of nodes. Use adjacency(T) to read it as a matrix.

Input arguments

G: A digraph object.

Output arguments

T: A digraph with the same nodes as G and the extra edges implied by reachability.

Example

Closure of a chain 1 -> 2 -> 3

G = digraph([1 2], [2 3]);
T = transclosure(G);
full(adjacency(T))

Output

ans = 3×3

     0     1     1
     0     0     1
     0     0     0

transclosure