Networkx start and end node

user_19424148 0
Viewed 109

Hi does anyone know how to get all the start node and the end of node of Network for digraph? If the graph is not a cycle and contain several branches, I would like to get the start node and all of the end node(can be more than 1 if there are more than 1 branch) The reason I wanted to get those node is because I would like to print all the path (there is a built in function called simple path in networtkx) and this require start and end node

networkx python
2 Answers

For a directed acylic graph, NetworkX provides a function called topological_generations. This enables you to find nodes at the top and bottom of a tree structure, for example:

import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(1, 2), (2, 3), (3, 4), (3, 5), (3, 6)])

for tier in nx.topological_generations(G):
    print(tier)

Output

[1]
[2]
[3]
[4, 5, 6]

Grabbing just the first and last tiers, assuming there are 3 or more:

first, *middle, last = nx.topological_generations(G)
print(f'First tier:  {first}')
print(f'Lowest tier: {last}')
paths = list(nx.all_simple_paths(G, 1, 6))
print(f'Simple paths from 1 to 6: {paths}')

Output

First tier:  [1]
Lowest tier: [4, 5, 6]
Simple paths from 1 to 6: [[1, 2, 3, 6]]
user_20881550

The start nodes will be the ones with an in-degree of 0. The end nodes will have an out-degree of 0.

Here's an example digraph: Example directed graph with cycles Note that nodes A, B, and C are start nodes, numbered nodes have edges pointing both in and out, and nodes X, Y, and Z are end nodes. Here's the code to generate that graph:

import matplotlib.pyplot as plt
import networkx as nx

D = nx.DiGraph()

edges = [('A', '1'), ('B', '2'), ('C', '3'), ('1', '2'),
         ('2', '3'), ('3', '4'), ('3', '5'), ('5', '6'),
         ('4', '5'), ('5', '4'), ('5', '2'), ('2', '6'),
         ('6', '4'), ('4', 'X'), ('5', 'Y'), ('6', 'Z')]
D.add_edges_from(edges)

pos = nx.spring_layout(D)
fig, ax = plt.subplots(figsize=(10, 5))

nx.draw_networkx_nodes(D, pos, ax=ax, node_size=500, node_color="#acddc5", edgecolors='g')
nx.draw_networkx_labels(D, pos, ax=ax, font_weight='bold', font_size=12)
nx.draw_networkx_edges(D, pos, ax=ax, edgelist=edges, edge_color="g")

plt.show()

Now I can iterate over all of the nodes looking for the ones with in-degree of 0 and out-degree of 0 using the in_degree and out_degree functions. (Both functions return an iterator of tuples that contain (node, degree) of each node in the graph.)

start_nodes = [n for n, d in D.in_degree() if d == 0]
end_nodes = [n for n, d in D.out_degree() if d == 0]

print("Start nodes:", start_nodes)
print("End nodes:", end_nodes)

Output:

Start nodes: ['A', 'B', 'C']
End nodes: ['X', 'Y', 'Z']
Bill_the_Lizard_12880
Related