# TransitiveClosureGraph doesn't return self-loops for nodes that are in a cycle

This is from boost library documentation:

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.

For example from C++ Boost library (left: the input graph) (right: the transitive closure of the input graph):

Using mathematica for the same graph ignores the self-loops :

I kinda fixed it by finding cycles and adding loops:

loopyTransitiveClosure[g_] :=
(candidate = TransitiveClosureGraph[g];
cycles = Flatten@FindCycle[g];
Do[If[MemberQ[cycles, i \[DirectedEdge] _],
candidate = EdgeAdd[candidate, i \[DirectedEdge] i]],{i,VertexList[G]}];
candidate)


And it works fine:

But I bet this is so inefficient. How can I implement it from scratch to work efficient and handle the loopy cases ? Especially I need to get O(|V||E|) complexity that Boost Library provides.

• The boost definition is correct. Why is Mma's behavior not a bug? – Alan Oct 11 '15 at 16:32
• As further evidence that TransitiveClosureGraph should be considered buggy, note that even if the original graph includes self loops, these will be omitted by its purported transitive closure! – Alan Oct 11 '15 at 16:56
• This persists in 11.1. Shouldn't it get the bug tag? – Alan Jun 13 '17 at 18:09

Combinatorica does that out of the box:
Needs["Combinatorica"]
g = SystemGraph@list
myG = SystemGraph[DirectedEdge @@@ ToOrderedPairs@gCT]

The usual caveats when using Combinatorica` apply.