CODEWITHSUNDEEP
pythongraphnetworkx
Danila Kulakov
Danila Kulakov

Reputation: 1142

Networkx: Finding the shortest path to one of multiple nodes in Graph

I have a graph of different locations: 

import networkx as nx

G = nx.Graph()
for edge in Edge.objects.all():
    G.add_edge(edge.from_location, edge.to_location, weight=edge.distance)

The locations (nodes) have different types (toilets, building entrances, etc.) I need to find the shortest way from some given location to any location of a specific type. (For example: Find the nearest entrance from a given node.)

Is there some method in the Networkx library to solve that without loops? Something like: 

nx.shortest_path(
     G,
     source=start_location,
     target=[first_location, second_location],
     weight='weight'
)

The result will be the shortest path to either the first_location or the second_location, if both locations are of the same type.

And is there some method that also returns path length?

Upvotes: 8

Views: 6378

Answers (1)

Ram Narasimhan
Ram Narasimhan

Reputation: 22516

We will do it in three steps.

  • Step 1: Let's create a dummy graph to illustrate
  • Step 2: Plot the graph and color nodes to indicate edge lengths and special node types (toilets, entrances etc.)
  • Step 3: From any given node (source) calculate shortest path to all reachable nodes, then subset to the node types of interest and select path with the minimum length.

The code below can definitely be optimized, but this might be easier to follow.

Step 1: Create the graph

edge_objects = [(1,2, 0.4), (1, 3, 1.7), (2, 4, 1.2), (3, 4, 0.3), (4 , 5, 1.9), 
(4 ,6, 0.6), (1,7, 0.4), (3,5, 1.7), (2, 6, 1.2), (6, 7, 0.3), 
(6, 8, 1.9), (8,9, 0.6)]

toilets = [5,9] # Mark two nodes (5 & 9) to be toilets
entrances = [2,7] # Mark two nodes (2 & 7) to be Entrances
common_nodes = [1,3,4,6,8] #all the other nodes

node_types = [(9, 'toilet'), (5, 'toilet'),
              (7, 'entrance'), (2, 'entrance')]

#create the networkx Graph with node types and specifying edge distances
G = nx.Graph()

for n,typ in node_types:
    G.add_node(n, type=typ) #add each node to the graph

for from_loc, to_loc, dist in edge_objects:
    G.add_edge(from_loc, to_loc, distance=dist) #add all the edges

Step 2: Draw the graph

#Draw the graph (optional step)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)
edge_labels = nx.get_edge_attributes(G,'distance')
nx.draw_networkx_edge_labels(G, pos, edge_labels = edge_labels)
nx.draw_networkx_nodes(G, pos, nodelist=toilets, node_color='b')
nx.draw_networkx_nodes(G, pos, nodelist=entrances, node_color='g')
nx.draw_networkx_nodes(G, pos, nodelist=common_nodes, node_color='r')
plt.show()

enter image description here

Step 3: create small functions to find the shortest path to node type

def subset_typeofnode(G, typestr):
    '''return those nodes in graph G that match type = typestr.'''
    return [name for name, d in G.nodes(data=True) 
            if 'type' in d and (d['type'] ==typestr)]

#All computations happen in this function
def find_nearest(typeofnode, fromnode):

    #Calculate the length of paths from fromnode to all other nodes
    lengths=nx.single_source_dijkstra_path_length(G, fromnode, weight='distance')
    paths = nx.single_source_dijkstra_path(G, fromnode)

    #We are only interested in a particular type of node
    subnodes = subset_typeofnode(G, typeofnode)
    subdict = {k: v for k, v in lengths.items() if k in subnodes}

    #return the smallest of all lengths to get to typeofnode
    if subdict: #dict of shortest paths to all entrances/toilets
        nearest =  min(subdict, key=subdict.get) #shortest value among all the keys
        return(nearest, subdict[nearest], paths[nearest])
    else: #not found, no path from source to typeofnode
        return(None, None, None)

Test:

 find_nearest('entrance', fromnode=5)

produces:

 (7, 2.8, [5, 4, 6, 7])

Meaning: The nearest 'entrance' node from 5 is 7, the path length is 2.8 and the full path is: [5, 4, 6, 7]. Hope this helps you move forward. Please ask if anything is not clear.

Upvotes: 10

Related Questions