CODEWITHSUNDEEP
pythonnetworkxdirected-graph
Alan
Alan

Reputation: 9620

compute transitive closure of directed graph with networkx

My efforts to find how to compute transitive closure of directed graph with networkx have come up surprisingly empty. It seems unlikely that this is not in networkx, so ... where is it? (I am aware that Sage includes this functionality.)

Upvotes: 1

Views: 1148

Answers (1)

Aric
Aric

Reputation: 25289

There is no transitive closure function in NetworkX. But I think you can do it in one line :-). (untested)

In [1]: import networkx as nx

In [2]: G = nx.DiGraph([(1, 2), (2, 3), (3, 2), (3, 4)])

In [3]: H = nx.DiGraph([(u,v,{'d':l}) for u,adj in nx.floyd_warshall(G).items() for v,l in adj.items() if l > 0 and l < float('inf')])

In [4]: H.adj
Out[4]: 
{1: {2: {'d': 1.0}, 3: {'d': 2.0}, 4: {'d': 3.0}},
 2: {3: {'d': 1.0}, 4: {'d': 2.0}},
 3: {2: {'d': 1.0}, 4: {'d': 1.0}},
 4: {}}

Upvotes: 1

Related Questions