![[Experimental]](figures/lifecycle-experimental.svg)
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.
Value
A new graph object representing the transitive closure. The returned graph will have the same directedness as the input.
See also
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()
Author
Fabio Zanini fabio.zanini@unsw.edu.au
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)
#> ── <igraph> ───────────────────────────────────────────────────────── d87fd33 ──
#> ℹ directed
#> ℹ 4 vertices · 6 edges
#>
#> ── Edges ───────────────────────────────────────────────────────────────────────
#> [1] 1 → 2 1 → 3 1 → 4 2 → 3 2 → 4 3 → 4
# 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> ───────────────────────────────────────────────────────── 7bc11eb ──
#> ℹ undirected
#> ℹ 4 vertices · 2 edges
#>
#> ── Edges ───────────────────────────────────────────────────────────────────────
#> [1] 1 ─ 2 3 ─ 4