Find end node in directed graph

Question

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)

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)]

Can you remove and G.in_degree(x)==1 from the endnode list comp? — ggorlen
– ggorlen, Commented Aug 27, 2019 at 16:08
Isn't G.out_degree(x)==0 sufficient to define and end node? — Dan
– Dan, Commented Aug 27, 2019 at 16:08

Prune · Accepted Answer · 2019-08-27 16:08:08Z

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.

What do you do in case there are multiple nodes without "in" or "out" edges?
Then you have multiple start and end nodes. I don't see the difficulty here. Each of OP's examples have two start nodes.

Collectives™ on Stack Overflow

Find end node in directed graph

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related