`transreduction`

Transitive reduction of a directed acyclic graph.

Category: Mathematics > Graph and Network Algorithms

Syntax

R = transreduction(G)

Returns the digraph with the fewest edges that has the same reachability as G.

Description

An edge u -> v is redundant when another path from u to v already exists. The transitive reduction removes every redundant edge while preserving which nodes can reach which.

It is the inverse of transclosure in the sense that both graphs have the same closure. A typical use is to draw a dependency diagram without clutter.

Input arguments

G: A digraph object, normally acyclic.

Output arguments

R: A digraph with the same nodes and only the edges that are not implied by longer paths.

Example

Dropping the shortcut edge 1 -> 3

G = digraph([1 2 1], [2 3 3]);
R = transreduction(G);
R.Edges

Output

ans = 2×1 table

    EndNodes
    ________

     1    2 
     2    3

transreduction