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?
Returns the shortest weighted path from source to target in G. Uses Dijkstra's Method to compute the shortest weighted path between two nodes in a graph. If this is a string, then edge weights will be accessed via the edge attribute with this key (that is, the weight of the edge joining u to v will be G.
graph length will be N, and j is not same as i is in the list graph[i] exactly once, if and only if nodes i and j are connected. We have to find the length of the shortest path that visits every node. We can start and stop at any node, we can revisit nodes multiple times, and we can reuse edges.
In general, there can be multiple shortest paths in a graph. In particular, you can use Djikstra's algorithm to compute shortest paths and this algorithm can return multiple paths from any node A to any other node B.
We will do it in three steps.
The code below can definitely be optimized, but this might be easier to follow.
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
#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()
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With