# Finding the root nodes in a networkx.Graph() and paths between those nodes

This should be a simple question, but one I am not sure how to answer since I am new to the networkx api.

The graphs I will be working with will not be directed and be acyclic.

I have created a nx.Graph(), added nodes and edges, can draw it with nx.draw(G), etc.

What I want to find are two things:

1. What are the root nodes? i.e. those nodes with only a single edge
2. For each root node, what are the edges leading to each other root node?

I have attached some sample code, which is based on my real case, creating a graph. Drawing the graph looks like: The answer to #1 would be the nodes ( 5, 6 ), ( 6, 7 ), and (14, 15 ). How can I use networkx to return those three nodes?

There are three possible paths between the nodes. One of the answers to #2 is:

1. ( 5, 6 ), ( 4, 5 ), ( 3, 4 ), ( 1, 2 ), ( 11, 12 ), ( 12, 13 ), ( 13, 14 ), ( 14, 15 )

2. ( 5, 6 ), ( 4, 5 ), ( 3, 4 ), ( 1, 2 ), ( 10, 11 ), ( 9, 10 ), ( 8, 9 ), ( 7, 8 ), ( 6, 7 )

3. ( 14, 15 ), ( 13, 14 ), ( 12, 13 ), ( 11, 12 ), ( 1, 2 ), ( 10, 11 ), ( 9, 10 ), ( 8, 9 ), ( 7, 8 ), ( 6, 7 )

Clearly, three paths could be reversed and still be part of a valid answer.

How can I use networkx to return those three paths?

``````import networkx as nx

class PairToNXObject:

def __init__(self, pair):
self.pair = pair

def __eq__(self, other):
return hash( self ) == hash( other )

def __hash__(self):
return hash( f'( {self.pair}//{self.pair} )' )

def __repr__(self):
return f'( {self.pair} {self.pair} )'

coordinateList = [[(1, 2),
(3, 4),
(4, 5),
(5, 6)],
[(6, 7),
(7, 8),
(8, 9),
(9, 10),
(10, 11),
(1, 2)],
[(1, 2),
(11, 12),
(12, 13),
(13, 14),
(14, 15)]]

G = nx.Graph()

for coordinates in coordinateList:

nodes = []

for coordinate in coordinates:
node = PairToNXObject( coordinate )

nodes.append( node )

for x in range( 0, len( nodes ) - 1 ):
G.add_edge( nodes[x], nodes[ x + 1 ] )

nx.draw(G, with_labels = True, node_color='#eeeeee' )
``````

### >Solution :

You can use `degree` to identify the nodes with a single edge, and `shortest_simple_paths` to find the path between `combination` of nodes:

``````from itertools import combinations

# find roots
roots = {n for n, d in G.degree() if d==1}
# {( 14 15 ), ( 5 6 ), ( 6 7 )}

# get shortest path between pairs of roots
out = [next(nx.shortest_simple_paths(G, a, b), None)
for a,b in combinations(roots, 2)]
``````

Output:

``````[[( 5 6 ), ( 4 5 ), ( 3 4 ), ( 1 2 ), ( 11 12 ), ( 12 13 ), ( 13 14 ), ( 14 15 )],
[( 5 6 ), ( 4 5 ), ( 3 4 ), ( 1 2 ), ( 10 11 ), ( 9 10 ), ( 8 9 ), ( 7 8 ), ( 6 7 )],
[( 14 15 ), ( 13 14 ), ( 12 13 ), ( 11 12 ), ( 1 2 ), ( 10 11 ), ( 9 10 ), ( 8 9 ), ( 7 8 ), ( 6 7 )]]
``````

As dictionary:

``````out = {(a, b): next(nx.shortest_simple_paths(G, a, b), None)
for a,b in combinations(roots, 2)}
``````

Output:

``````{(( 5 6 ), ( 14 15 )): [( 5 6 ), ( 4 5 ), ( 3 4 ), ( 1 2 ), ( 11 12 ), ( 12 13 ), ( 13 14 ), ( 14 15 )],
(( 5 6 ), ( 6 7 )): [( 5 6 ), ( 4 5 ), ( 3 4 ), ( 1 2 ), ( 10 11 ), ( 9 10 ), ( 8 9 ), ( 7 8 ), ( 6 7 )],
(( 14 15 ), ( 6 7 )): [( 14 15 ), ( 13 14 ), ( 12 13 ), ( 11 12 ), ( 1 2 ), ( 10 11 ), ( 9 10 ), ( 8 9 ), ( 7 8 ), ( 6 7 )]}
``````