transitive_closure

graph_tool.topology.transitive_closure(g)

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

[transitive-boost]

http://www.boost.org/libs/graph/doc/transitive_closure.html

[transitive-wiki]

http://en.wikipedia.org/wiki/Transitive_closure

Examples

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