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

我想确定网络边缘的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)

救命！

最佳答案

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

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

关于python - 高效(空间)网络邻居？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6852759/