first of all I am really new to python in genereal and espcially to networkx. I got a question regarding the networkx shortest_path(G,source,target)
function. For a series of found positions (let´s call them x), I would like to find the shortest path to another series of found positions (let´s call them y). I would like to find the shortest path for every x to only one of the points in y, namely the point that has the smallest length.
So if x has two y´s in reach and the length (shortest_path_length(G,source,target)
) for the first path is 5 and the path for the second is 10, I would like to only take the path with length 5 and safe the positions of all nodes for this path in a list and ignore the other paths.
I am using a skeletonized structure to do so. I am looking for dead ends (which is x, with degree == 1
) and junctions (which is y, with degree >= 3
)
I tried it with for loops, but did not work correct. My source would be x (deadends) and my target would be the closest y position (junction) I asked another question here, where my problem and part of the code is already written down. I will include a link, so that I do not flood this question with the same code again. Thank you to everyone helping me out.
Finding dead ends in a skeletonized canal structure
Advertisement
Answer
You can compute all shortest paths from a given source with nx.single_source_shortest_paths
. You then just need to filter the results looking for paths to branchpoints, and then select the shortest of those.
#!/usr/bin/env python """ Find the shortest path between two sets of nodes of interest. """ import random import networkx as nx # create a reproducible test data set random.seed(10) g = nx.random_tree(15) # determine the leaves and branchpoints leaves = [node for node in g.nodes() if g.degree(node) == 1] branchpoints = [node for node in g.nodes() if g.degree(node) > 2] # find the shortest path from each leaf to any of the branchpoints shortest_paths = dict() # leaf -> path closest_branchpoint = dict() # leaf -> branchpoint for leaf in leaves: # find paths to all other nodes paths_to_all_other_nodes = nx.single_source_shortest_path(g, leaf) # filter for paths to branchpoints paths_to_branchpoints = {node : path for node, path in paths_to_all_other_nodes.items() if node in branchpoints} # determine the closest branchpoint and save out branchpoint and corresponding path closest_branchpoint[leaf] = min(paths_to_branchpoints, key=lambda x: len(paths_to_branchpoints[x])) shortest_paths[leaf] = paths_to_branchpoints[closest_branchpoint[leaf]] # print results for leaf in leaves: print(f"{leaf} -> {closest_branchpoint[leaf]} : {shortest_paths[leaf]}") # plot for visual confirmation import matplotlib.pyplot as plt from netgraph import Graph # pip install netgraph Graph(g, node_layout='dot', node_labels=True, node_label_offset=0.05, node_label_fontdict=dict(size=20)) plt.show()
This yields:
1 -> 9 : [1, 9] 2 -> 0 : [2, 0] 5 -> 7 : [5, 6, 7] 8 -> 9 : [8, 9] 11 -> 13 : [11, 13] 12 -> 7 : [12, 7] 14 -> 13 : [14, 10, 4, 13]