CODEWITHSUNDEEP
pythongraphnetworkxpyvis
mark mcmurray
mark mcmurray

Reputation: 1671

Does networkx provide a method to create a subgraph of all possible paths which can be taken from one node?

I have a graph showing the relationships between objects where if object A interacts with object B, and object B interacts with object C, I must assume object A could transitively interact with object C.

I can get a set of all of these paths using the nx.descendants.

I would also like to display a graph showing these transitive relationships - is there a similar method that returns a graph rather than a set?

Upvotes: 0

Views: 786

Answers (1)

Andrew Eckart
Andrew Eckart

Reputation: 1726

You can do this easily by taking the descendants (plus the source) and making a copy of the subgraph induced by these nodes:

In [1]: import networkx as nx

In [2]: G = nx.DiGraph()

In [3]: G.add_edges_from([("a", "b"), ("b", "c"), ("c", "d"), ("b", "e")])

In [4]: descendants = nx.descendants(G, "b")

In [5]: descendants
Out[5]: {'c', 'd', 'e'}

In [6]: descendants.add("b")

In [7]: H = G.subgraph(descendants).copy()

In [8]: H.adj
Out[8]: AdjacencyView({'b': {'c': {}, 'e': {}}, 'c': {'d': {}}, 'd': {}, 'e': {}})

In [9]: list(H.edges)
Out[9]: [('b', 'c'), ('b', 'e'), ('c', 'd')]

Note that this will only include edges which exist in the original graph, e.g. ('b', 'c') and ('c', 'd'), but not ('b', 'd'). This relationship is implied by the structure of the graph, but to add edges which fill in these implied relationships (the reachability relation), you can take the transitive closure:

In [15]: list(nx.transitive_closure(H).edges)
Out[15]: [('b', 'c'), ('b', 'e'), ('b', 'd'), ('c', 'd')]

These algorithms actually work for all directed graphs, not just DAGs.

Upvotes: 2

Related Questions