여러 소스 및 대상 노드에 대한 Networkx 최단 경로 분석 (Networkx Shortest Path Analysis on multiple source and target nodes)

문제 설명

여러 소스 및 대상 노드에 대한 Networkx 최단 경로 분석 (Networkx Shortest Path Analysis on multiple source and target nodes)

내가 가지고 있는 것:

• 학교 점수의 지오데이터프레임(출처 ‑ 총 18)
• 병원 pt의 지오데이터프레임(목표 ‑ 총 27)
• 투영된 Osmnx 그래프(노드 + 에지)

내가 원하는 것:

• 각각에 대한 최단 경로 기하 도형을 포함하는 지리 데이터 프레임 각 학교의 병원(각각 경로가 있는 테이블의 총 486 [18*27] 기능) 예

학교/병원에서 읽은 후 osmnx 거리 그래프를 당겨 투영

소스 및 타겟 포인트 모두에 대해 가장 가까운 osm 노드를 가져오는 함수를 정의할 수 있습니다.

# import neceessary modules
import pandas as pd
import geopandas as gpd
import osmnx as ox
import networkx as nx
import matplotlib.pyplot as plt
from pyproj import CRS
from shapely.geometry import Polygon, Point, LineString
)

# read in file
hosp_fp = r'vtData/hospitals.shp'
school_fp = r'vtData/schools.shp'
​
# read files
hospitals = gpd.read_file(hosp_fp)
schools = gpd.read_file(school_fp)

#### skip the reading osmnx part (the error isn't here and, yes,everything in same crs) ######

# Create function to find nearest node
def get_nearest_node(points, graph):
    # a function that finds the nearest node
    # params: points (a gdf of points with an x and y column); graph (an osm network graph)
    points['nearest_osm'] = None
    for i in tqdm(points.index, desc='find nearest osm node from input points', position=0):
        points.loc[i, 'nearest_osm'] = ox.get_nearest_node(graph, [points.loc[i, 'y'], points.loc[i, 'x']], method='euclidean') # find the nearest node from hospital location
    return(points)

# use the function to find each destination point nearest node
## returns the original gdfs with corresponding osmid column
source = get_nearest_node(schools, graph)
target = get_nearest_node(hospitals, graph)

# extract osmid's from list
src_list = list(source['nearest_osm'])
trg_list = list(target['nearest_osm'])

### WHERE I AM STUCK ####
# a function meant to construct shortest path routes to each target from each source

def get_routes(graph, src_list, trg_list):
    # a function that constructs a shortest routes to each target from the source
    # params: graph_proj (a projected osmnx graph); src (source pts); trg (target pts)

    # an empty list to append route linestring geometries to
    routes = []

    # a loop to construct all shortest path geometries
    for src, trg in zip(src_list, trg_list):
        sp = nx.shortest_path(graph, source=src, target=trg, 
        weight='length')
        routes.append(sp)
        print(len(routes))

486개의 경로(각 소스 및 타겟에 대해 하나씩)를 반환하는 대신 18개 포인트 목록 가져오기(기본적으로 각 학교에 대해 27개의 최단 경로(총 병원 수)를 계산하는 것이 아니라 소스 및 대상 포인트의 해당 인덱스를 기반으로 경로를 계산하는 것입니다.

여기에서 ,경로라는 새 지리 데이터 프레임에 목록을 추가하지만 486개 경로 중 18개만 가지고 있습니다.

참조 솔루션

방법 1:

You are looking for the cartesian product of your origins and destinations, rather than zipping them together. Example:

import numpy as np
import osmnx as ox
from itertools import product
ox.config(log_console=True)

# get a graph and add edge travel times
G = ox.graph_from_place('Piedmont, CA, USA', network_type='drive')
G = ox.add_edge_travel_times(ox.add_edge_speeds(G))

# randomly choose 10 origins and 10 destinations
n = 10
origs = np.random.choice(G.nodes, size=n)
dests = np.random.choice(G.nodes, size=n)

# calculate 100 (10 origins x 10 destinations) shortest paths
paths = []
for o, d in product(origs, dests):
    path = ox.shortest_path(G, o, d, weight='travel_time')
    paths.append(path)

len(paths) #100

(by Derrick Burt、gboeing)

참조 문서

1. Networkx Shortest Path Analysis on multiple source and target nodes (CC BY‑SA 2.5/3.0/4.0)