[?] Get a TransitiveClosureGraph[] with loops?

Questions
1

Here is a simple example:

In[1]:= TransitiveClosureGraph[{1->2, 2->3, 3->1}]//AdjacencyMatrix//MatrixForm

Out[1]//MatrixForm= 0   1   1

                    1   0   1

                    1   1   0

This produces the graph with the adjacency matrix of {{0,1,1},{1,0,1},{1,1,0}}, but I expected the diagonal elements to be 1 as well, i.e. a loop for each vertex. At least for a binary relation that would be the case, so I don’t understand why the transitive closure for a graph is ignoring the loops. By the definition of transitive closure on MathWorld definition it is a graph which contains an edge {u,v} whenever there is a directed path from u to v. Well, in our case there is a directed path from 1 to 1, namely: 1->2, 2->3, 3->1. And likewise for the nodes 2 and 3. What am I missing here? Thank you.

2

Here’s a naïve implementation that produces self-loops.

Multigraphs are not supported by this implementation and the input must be a proper Graph object, not a list of rules.

ClearAll[transitiveClosureGraph]
transitiveClosureGraph::multi = "Multigraphs are not supported.";
transitiveClosureGraph::mixed = "Mixed graphs are not supported.";
transitiveClosureGraph[graph_?MixedGraphQ, OptionsPattern[]] := (Message[transitiveClosureGraph::mixed]; $Failed)
transitiveClosureGraph[graph_?MultigraphQ, OptionsPattern[]] := (Message[transitiveClosureGraph::multi]; $Failed)
transitiveClosureGraph[graph_?GraphQ, opt : OptionsPattern[Graph]] :=    
  With[{am = AdjacencyMatrix[graph]},
  AdjacencyGraph[
   VertexList[graph],
   FixedPoint[Unitize[am + am.#] &, am],
   DirectedEdges -> DirectedGraphQ[graph],
   opt
   ]
  ]

Mathematica graphics

P.S. I do not think that it is unreasonable for this function to return simple graphs, although there is also value in preserving those self-loops. What is more useful depends on the specific application.

3

Interestingly, the transitive_closure() function in networkx (a python package) also doesn’t create loops:

$ ipython
Python 3.6.4 (default, Dec 20 2017, 09:47:54) 
Type 'copyright', 'credits' or 'license' for more information
IPython 6.2.1 -- An enhanced Interactive Python. Type '?' for help.

In [1]: import networkx as nx

In [2]: import numpy as np

In [3]: a = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])

In [4]: a
Out[4]: 
array([[0, 1, 1],
       [1, 0, 1],
       [1, 1, 0]])

In [5]: G = nx.from_numpy_matrix(a, create_using=nx.MultiDiGraph())

In [6]: T = nx.transitive_closure(G)

In [7]: nx.to_numpy_matrix(T)
Out[7]: 
matrix([[0., 2., 2.],
        [2., 0., 2.],
        [2., 2., 0.]])

The value ‘2’ simply means two edges. But the diagonal values are all 0, just like in Mathematica. I am not sure why.

4

Thank you, that is a very useful function. So, is the conclusion that this behaviour of TransitiveClosureGraph[] function is expected and not a bug? I just want to know that I can trust this function not to drop something else as well, not just those loops :slight_smile:

5

I would definitely not call this a bug. It’s a question of definition.

When people talk about “graphs”, they may mean different things. It is very common to mean simple graphs, which exclude self-loops and multiple edges.

There is no reason to worry about wrong results based on this observation.

However, if you also work with TransitiveReductionGraph, you should know that this function is buggy. For reasons that I can’t possibly imagine, Wolfram hasn’t fixed this bug for 3 years now. Sometimes I really think that they just abandoned development of the graph functionality. Could there be any other explanation for not fixing such a nasty wrong-result bug despite multiple reports???

https://mathematica.stackexchange.com/questions/83852/question-about-transitivereductiongraph

6

I gave an implementation of transitive reduction over at StackExchange, to work around the bug in TransitiveReductionGraph.

7

Thank you, I noticed some other very cool stuff you have written (e.g. MaTeX) which I have now installed! :slight_smile: