Я хотел бы определить соседей K-го порядка по ребру в сети, в частности, соседей большого набора улиц.Например, у меня есть улица, на которую мне интересно смотреть, назовите ее центральной улицей.Для каждой целевой улицы я хочу найти улицы с пересечением, это соседи первого порядка.Затем для каждой из тех улиц, которые имеют пересечение с центральной улицей, я хотел бы найти своих соседей (это были бы соседи второго порядка) и т. Д. ...
Расчет соседей первого порядка с использованием ArcGIS'Библиотека геообработки (arcpy) заняла 6+ часов, соседи второго порядка занимают 18+ часов.Излишне говорить, что я хочу найти более эффективное решение.Я создал словарь Python, который имеет ключи на каждой улице и содержит связанные улицы в качестве значений.Например:
st2neighs = {street1: [street2, street3, street5], street2: [street1, street4], ...}.
улица 1 подключена к улице 2, 3, 5;улица 2 соединена с улицами 1 и 4;и т. д. В районе исследования около 30 000 улиц, большинство из которых имеют менее 7 соединенных улиц. маринованная версия данных, использованных в приведенном ниже коде ЗДЕСЬ .
Я предполагал, что знание соседей первого порядка позволит мне эффективно отслеживать соседей более высокого порядка,Но следующий код дает неверные результаты:
##Select K-order neighbors from a set of sampled streets.
##saves in dictionary format such that
##the key is the sampled street and the neighboring streets are the values
##################
##IMPORT LIBRARIES
##################
import random as random
import pickle
#######################
##LOAD PICKLED DATA
#######################
seg_file = open("seg2st.pkl", "rb")
st_file = open("st2neighs.pkl", "rb")
seg2st = pickle.load(seg_file)
st2neigh = pickle.load(st_file)
##################
##DEF FUNCTIONS
##################
##Takes in a dict of segments (key) and their streets (values).
##returns the desired number of sampled streets per segment
##returns a dict keyed segment containing tlids.
def selectSample(seg2st, nbirths):
randSt = {}
for segK in seg2st.iterkeys():
ranSamp = [int(random.choice(seg2st[segK])) for i in xrange(nbirths)]
randSt[segK] = []
for aSamp in ranSamp:
randSt[segK].append(aSamp)
return randSt
##Takes in a list of all streets (keys) and their first order neighbors (values)
##Takes in a list of sampled streets
##returns a dict of all sampled streets and their neighbors.
##Higher order selections should be possible with findMoreNeighbors
##logic is the same but replacing sample (input) with output from
##findFirstNeighbors
def findFirstNeighbors(st2neigh, sample):
compSts = {}
for samp in sample.iterkeys():
for rSt in sample[samp]:
if rSt not in compSts:
compSts[rSt] = []
for compSt in st2neigh[rSt]:
compSts[rSt].append(compSt)
return compSts
def findMoreNeighbors(st2neigh, compSts):
for aSt in compSts:
for st in compSts[aSt]:
for nSt in st2neigh[st]:
if nSt not in compSts[aSt]:
compSts[aSt].append(nSt)
moreNeighs = compSts
return moreNeighs
#####################
##The nHoods
#####################
samp = selectSample(seg2st, 1)
n1 = findFirstNeighbors(st2neigh, samp)
n2 = findMoreNeighbors(st2neigh, n1)
n3 = findMoreNeighbors(st2neigh, n2)
#####################
##CHECK RESULTS
#####################
def checkResults(neighList):
cntr = {}
for c in neighList.iterkeys():
cntr[c] = 0
for a in neighList[c]:
cntr[c] += 1
return cntr
##There is an error no streets **should** have 2000+ order neighbors
c1 = checkResults(n1)
c2 = checkResults(n2)
c3 = checkResults(n3)
Справка!