transitive_closure: Transitive closure of a graph

In igraph: Network Analysis and Visualization

Transitive closure of a graph

Description

Computes the transitive closure of a graph. The resulting graph will have an edge from vertex i to vertex j if j is reachable from i in the original graph.

The transitive closure of a graph is a new graph where there is an edge between any two vertices if there is a path between them in the original graph. For directed graphs, an edge from i to j is added if there is a directed path from i to j. For undirected graphs, this is equivalent to connecting all vertices that are in the same connected component.

Usage

transitive_closure(graph)

Arguments

graph

The input graph. It can be directed or undirected.

Value

A new graph object representing the transitive closure. The returned graph will have the same directedness as the input.

Related documentation in the C library

transitive_closure()

Author(s)

Fabio Zanini [e-mail]

See Also

distances(), are_adjacent()

Other functions for manipulating graph structure: +.igraph(), add_edges(), add_vertices(), complementer(), compose(), connect(), contract(), delete_edges(), delete_vertices(), difference(), difference.igraph(), disjoint_union(), edge(), igraph-minus, intersection(), intersection.igraph(), path(), permute(), rep.igraph(), reverse_edges(), simplify(), union(), union.igraph(), vertex()

Examples

# Directed graph
g <- make_graph(c(1, 2, 2, 3, 3, 4))
tc <- transitive_closure(g)
# The closure has edges 1->2, 1->3, 1->4, 2->3, 2->4, 3->4
print_all(tc)

# Undirected graph - connects all vertices in same component
g2 <- make_graph(c(1, 2, 3, 4), directed = FALSE)
tc2 <- transitive_closure(g2)
# Full graph on vertices 1, 2 and full graph on vertices 3, 4
print_all(tc2)

igraph documentation built on April 21, 2026, 5:06 p.m.