({{, (RefLink[TransitiveClosureGraph, paclet:ref/TransitiveClosureGraph])[g] 
gives the transitive closure of the graph g.}, {, (RefLink[TransitiveClosureGraph, paclet:ref/TransitiveClosureGraph])[{v->w,…}]
uses rules v->w to specify the graph g. }})

OpenersNotesSection(Spacer1)Details and Options

(RefLink[TransitiveClosureGraph, paclet:ref/TransitiveClosureGraph]) is also known as reachability graph.

(RefLink[TransitiveClosureGraph, paclet:ref/TransitiveClosureGraph])[g] gives a graph with the same vertices as in g, and a vertex u is connected to a vertex v if there is a path from u to v in g.

(RefLink[TransitiveClosureGraph, paclet:ref/TransitiveClosureGraph]) takes the same options as (RefLink[Graph, paclet:ref/Graph]).

Possible settings for the (RefLink[Method, paclet:ref/Method]) option include "Warshall", "Warren", and "Purdom". The default setting of (RefLink[Automatic, paclet:ref/Automatic]) switches among these methods depending on the graph given.

(RefLink[TransitiveClosureGraph, paclet:ref/TransitiveClosureGraph]) works with undirected graphs, directed graphs, and multigraphs.

OpenersPrimaryExamplesSection(Spacer1)Examples  (17)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

The transitive closure of a graph:

g=Graph[{1\[DirectedEdge]2,1\[DirectedEdge]3,1\[DirectedEdge]4,3\[DirectedEdge]4,2\[DirectedEdge]4,4\[DirectedEdge]5}];

TransitiveClosureGraph[g]

Highlight the original graph within its transitive closure:

HighlightGraph[%,g,GraphHighlightStyle->"Thick"]

OpenersExampleSection1(Spacer1)Scope  (5)

(RefLink[TransitiveClosureGraph, paclet:ref/TransitiveClosureGraph]) works with undirected graphs:

TransitiveClosureGraph[]

Directed graphs:

TransitiveClosureGraph[]

Multigraphs:

TransitiveClosureGraph[]

Use rules to specify the graph:

TransitiveClosureGraph[{1->2,1->5,2->3,3->4,4->5,3->6,4->6}]

(RefLink[TransitiveClosureGraph, paclet:ref/TransitiveClosureGraph]) works with large graphs:

g=RandomGraph[{10000,30000},DirectedEdges->True];

Timing[TransitiveClosureGraph[g];]

OpenersExampleSection2(Spacer1)Options  (3)

OpenersExampleSubsection0(Spacer1)Method  (3)

The method is automatically chosen depending on input:

TransitiveClosureGraph/@{,}

"Warshall" and "Warren" methods can be used for dense graphs:

g=;

TransitiveClosureGraph[g,Method-> "Warshall"]

TransitiveClosureGraph[g,Method-> "Warren"]

"Purdom" can be used for directed acyclic graphs:

g=;

TransitiveClosureGraph[g,Method-> "Purdom"]

OpenersExampleSection3(Spacer1)Applications  (2)

Find species in the food chain that would be affected if beetles were extinct:

g=ExampleData[{"NetworkGraph","SimpleFoodWeb"}]

AdjacencyList[TransitiveClosureGraph[g],"Beetle"]

Give a divisibility tree and find all divisors for each number:

g=;

TransitiveClosureGraph[g,VertexLabels->"Name"]

OpenersExampleSection4(Spacer1)Properties & Relations  (6)

The transitive closure graph has the same vertices as the original graph:

g=CycleGraph[4];

VertexList[TransitiveClosureGraph[g]]==VertexList[g]

An edge u->v is in the closure graph if there is a path from u to v in the original graph:

g=;

There is a path from 1 to 6 in the given graph, by no direct edge:

FindPath[g,1,6]

EdgeQ[g,1\[DirectedEdge]6]

There is a direct edge 1->6 in the transitive closure:

EdgeQ[TransitiveClosureGraph[g],1\[DirectedEdge]6]

The transitive closure of a connected undirected graph is a complete graph:

TransitiveClosureGraph[]

CompleteGraphQ[%]

Using transitive closure to find the reachability of each vertex in the graph:

g=;

AdjacencyList[TransitiveClosureGraph[g],1]

VertexOutComponent[g,1]

(RefLink[TransitiveClosureGraph, paclet:ref/TransitiveClosureGraph]) can be computed using (RefLink[GraphPower, paclet:ref/GraphPower]):

g=GridGraph[{2,3},DirectedEdges->True];

GraphPower[g,3]

TransitiveClosureGraph[g,VertexCoordinates->GraphEmbedding[g]]

The transitive closure is the same for a graph and its transitive reduction:

g=RandomGraph[{4,5},DirectedEdges->True];

{TransitiveClosureGraph[g],TransitiveClosureGraph[TransitiveReductionGraph[g]]}

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[TransitiveReductionGraph, paclet:ref/TransitiveReductionGraph])  ▪  (RefLink[VertexOutComponent, paclet:ref/VertexOutComponent])  ▪  (RefLink[GraphPower, paclet:ref/GraphPower])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Graph Operations and Modifications, paclet:guide/GraphModifications])}})}})