Python (GIS): How to convert geometric lines (in the form of a LineString) to a Complete Graph network using Networkx

Question

TL;DR How to convert a geodataframe of LineStrings to a Complete Graph with NetworkX?

I have a geodataframe of a collection of linestrings that geographically represent a road network (purple). I have 2 points (red and blue) representing A and B. I'd like to find the shortest route between A and B travelling along the road network.

I have converted the geodataframe to a network using momepy library:

road = gpd.read_file(input_road.shp)

#need to explode roads, as is multiline
exploded = road.explode(index_parts=True)

G = momepy.gdf_to_nx(exploded, approach="primal",length='mm_len',multigraph=True)

This successfully converts my road network to a networkx multigraph, whilst preserving distance (mm_len) between points.

Then I add points A and B to the network by getting the closest nodes on the road network to these points:

my_points = gpd.read_file(my_points)

#Firstly, need to convert the coordinates to a tuple of x,y coordinates
for my_point in my_points .geometry.values:
    coords_values = re.findall('[0-9.]+ [0-9.]+', str(my_point ))
    
    #convert list of strings separated by spaces, to a list of coords as list. 
    coords = [sub.split(' ') for sub in coords_values ][0]
    coords_tuple= tuple(map(float, coords ))
    coords_list.append(coords_tuple)

#add this coord tuple as a column in the dataframe
my_points["coords_syntax"] = coords_list

#this dictionary will be used to select the network nodes. The key is the coordinate tuple, and the attribute will be the 'Name' of the point
dict_df_mypoints = home.set_index('coords_syntax')['Name'].to_dict()   

#select the nearest node points on the road network to these coordinate tuples
A = list(G.nodes())

#iterate through dict of coords: my_points
for point in dict_df_mypoints :
    
    
    #get closest node (using KDTree) between point and the array of cords A generated above
    closest_node = A[scipy.spatial.KDTree(A).query(point)[1]]
    
    #make these above closest nodes have attribute my_point, with other attributes (dict_df[point])
    G.nodes[closest_node]['my_point'] = dict_df[point]

So now within all the nodes of my road network, I have 2 representing points A and B respectively. Their node key is the coordinate pair.

However, when I run the shortest_path algorithm between A and B I get this error:

nx.shortest_path(G,source = (455529.02164326626, 206374.9504608615),target = (454340.3426543578, 207204.53480888018))


>>NetworkXNoPath: No path between (455529.02164326626, 206374.9504608615) and (454340.3426543578, 207204.53480888018)

And when I check the edges of these nodes, they are only connected to their 2 neighbours, and no other node:

nx.single_source_shortest_path_length(G,source = (455529.02164326626, 206374.9504608615))

 >>{(455529.02164326626, 206374.9504608615): 0,
 >>(455582.6204962559, 206424.4603359318): 1,
 >>(455596.5948359391, 206455.62556823122): 2}

So with my road network, I think I need ALL my nodes to be connected to one another (rather than just to their neighbours) with edges, otherwise the shortest_path won't work. I need to make my network a Complete Graph. However, I have no idea how to do that- it can't be done with Momepy. However I am unsure how to create a NetworkX Graph from scratch whilst preserving the geographical distances between the nodes of the roadnetwork - this is what drew me to using Momepy in the first place. Advice would be appreciated, thanks :)

Answer 1

To answer your actual question (that is not in the title), I would use sjoin_nearest with idxmin to get the relevant nodes, then specify a weight (i.e, the distance) when asking for the shortest_path between the two points (A and B):

from shapely import Point

points = gpd.GeoDataFrame(
    {"point": [*"AB"]},
    geometry=gpd.points_from_xy(*zip(*[A, B])),
    crs=road.crs,
)
nodes = gpd.GeoDataFrame(
    {"node": G.nodes},
    geometry=list(map(Point, G.nodes)),
    crs=road.crs,
)

njoin = nodes.sjoin_nearest(points.assign(coo=[A, B]), distance_col="dis")
min_dis = njoin.loc[njoin.groupby("point")["dis"].idxmin()]

for u, v, d in zip(
    min_dis["node"], min_dis["coo"], min_dis["dis"],
): G.add_edge(u, v, mm_len=d)

a_to_b = nx.shortest_path(
    G, source=A, target=B, weight="mm_len",
)

NB: I used the "bubenec" road/dataset (provided by momepy) to do the plotting (see full code).