transitive_closure

transitive_closure#

graph_tool.topology.transitive_closure(g)[source]#

Return the transitive closure graph of g.

Notes

The transitive closure of a graph G = (V,E) is a graph G* = (V,E*) such that E* contains an edge (u,v) if and only if G contains a path (of at least one edge) from u to v. The transitive_closure() function transforms the input graph g into the transitive closure graph tc.

The time complexity (worst-case) is \(O(VE)\).

References

Examples

>>> g = gt.random_graph(30, lambda: (3, 3))
>>> tc = gt.transitive_closure(g)