CODEWITHSUNDEEP
pythongraphnetworkx
Eric G
Eric G

Reputation: 742

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:

visualized

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

Upvotes: 1

Views: 277

Answers (1)

mozway
mozway

Reputation: 261964

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

Upvotes: 3

Related Questions