This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English version of the page.

Note: This page has been translated by MathWorks. Click here to see
To view all translated materials including this page, select Country from the country navigator on the bottom of this page.


Transitive closure


H = transclosure(G)



H = transclosure(G) returns the transitive closure of graph G as a new graph, H. The nodes in H are the same as those in G, but H has additional edges. If there is a path from node i to node j in G, then there is an edge between node i and node j in H. For multigraphs with multiple edges between the same two nodes, the output graph replaces these with a single edge.


collapse all

Create and plot a directed graph.

G = digraph([1 2 3 4 4 4 5 5 5 6 7 8],[2 3 5 1 3 6 6 7 8 9 9 9]);

Find the transitive closure of graph G and plot the resulting graph. H contains the same nodes as G, but has additional edges.

H = transclosure(G);

The transitive closure information in H can be used to answer reachability questions about the original graph, G.

Determine the nodes in G that can be reached from node 1. These nodes are the successors of node 1 in the transitive closure graph, H.

N = successors(H,1)
N = 7×1


Input Arguments

collapse all

Input graph, specified as a digraph object. Use digraph to create a directed graph object.

Example: G = digraph([1 2],[2 3])

Output Arguments

collapse all

Transitive closure of G, returned as a digraph object. The table G.Nodes is copied to H, but any properties in G.Edges are dropped.

Use successors(H,n) to determine the nodes in G that are reachable from node n.

More About

collapse all

Transitive Closure

The transitive closure of a graph describes the paths between the nodes. If there is a path from node i to node j in a graph, then an edge exists between node i and node j in the transitive closure of that graph. Thus, for a given node in the graph, the transitive closure turns any reachable node into a direct successor (descendent) of that node.

Introduced in R2015b