2
$\begingroup$

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):

enter image description here enter image description here

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

enter image description here

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ The boost definition is correct. Why is Mma's behavior not a bug? $\endgroup$ – Alan Oct 11 '15 at 16:32
  • $\begingroup$ 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! $\endgroup$ – Alan Oct 11 '15 at 16:56
  • $\begingroup$ This persists in 11.1. Shouldn't it get the bug tag? $\endgroup$ – Alan Jun 13 '17 at 18:09
2
$\begingroup$

Combinatorica does that out of the box:

Needs["Combinatorica`"]
Needs["GraphUtilities`"]
list = DirectedEdge @@@ {{d, a}, {d, c}, {c, b}, {b, c}, {b, d}};
g = System`Graph@list
gComb = ToCombinatoricaGraph@g;
ShowGraph[gCT = Combinatorica`TransitiveClosure@gComb]
myG = System`Graph[DirectedEdge @@@ ToOrderedPairs@gCT]

Mathematica graphics Mathematica graphics

The usual caveats when using Combinatorica apply.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.