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:

- What are the root nodes? i.e. those nodes with only a single edge
- 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[0]}//{self.pair[1]} )' )
def __repr__(self):
return f'( {self.pair[0]} {self.pair[1]} )'
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 )
G.add_node( node )
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 )]}
```