# [✓] Get a TransitiveClosureGraph[] with loops?

Posted 10 months ago
856 Views
|
6 Replies
|
4 Total Likes
|
 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.
6 Replies
Sort By:
Posted 10 months ago
 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 ] ]  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.
Posted 10 months ago
 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 :)
Posted 10 months ago
 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.
Posted 10 months ago
 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
 I gave an implementation of transitive reduction over at StackExchange, to work around the bug in TransitiveReductionGraph.