python - 高效(空间)网络邻居？

Question

我想识别网络上边缘的 K 阶邻居，特别是一大组街道的邻居。例如，我有一条我感兴趣的街道，称之为焦点街道。对于每条焦点街道，我想找到共享交叉路口的街道，这些是一阶邻居。然后，对于与焦点街道共享交叉路口的每条街道，我想找到它们的邻居(这些将是二阶邻居)，依此类推......

使用 ArcGIS 地理处理库 (arcpy) 计算一阶邻域需要 6 个多小时，二阶邻域需要 18 个多小时。不用说，我想找到一个更有效的解决方案。我创建了一个 python 字典，它以每条街道为键，并包含连接的街道作为值。例如:

st2neighs = {street1: [street2, street3, street5], street2: [street1, street4], ...}.  

1号街道与2、3、5号街道相连；街道 2 与街道 1 和 4 相连；研究区域内约有 30,000 条街道，大多数街道相连的街道少于 7 条。 以下代码中使用的数据的腌制版本IS HERE 。

我认为了解一阶邻居将使我能够有效地跟踪更高阶邻居。但以下代码提供了不正确的结果:

##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)

救命!

Answer 1

在我看来，您想要实现的内容如下:http://en.wikipedia.org/wiki/Composition_of_relations

这实际上是一个简单的算法。令 R 为关系“是一阶邻居”，因此如果两条街道 x,y 在 R 中，则 x 是 y 的一阶邻居。因此，对于二阶邻居，您需要计算由 R 组成的 R。对于三阶邻居(由 R 组成的 R)，由 R 组成。依此类推。