CODEWITHSUNDEEP
pythonnetworkx
Bera
Bera

Reputation: 1949

Find end node in directed graph

I have many subgraphs like this one:

import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(2,1),(3,1),(1,4)])
nx.draw(G)

enter image description here

I want to find all start and endnodes. So I use:

startnodes = [x for x in G.nodes() if G.out_degree(x)==1 and G.in_degree(x)==0]
endnode = [x for x in G.nodes() if G.out_degree(x)==0 and G.in_degree(x)==1][0]
print(startnodes, endnode)
[2, 3] 4

But some of the subgraphs look like below, with 2 in degrees for end node. How can I find end node for this?

G.add_edges_from([(2,1),(3,1)]

enter image description here

Upvotes: 5

Views: 2521

Answers (1)

Prune
Prune

Reputation: 77910

There is only one consideration for each:

  • An end-node is one without any "out" edges.
  • A start-node is one without any "in" edges.

That's all. If you need to identify your sub-graphs as well, then simply perform any of the standard closure operations from each start node. Where those sub-graphs have common nodes, merge the sub-graphs.

Upvotes: 7

Related Questions