查找邻域数据的最有效方法

Question

问题

我的程序生成几组数据，这些数据使我能够在tkinter画布上呈现一个顶点网络及其连接。我需要能够找到网络中每个顶点的第N个邻居。

我的代码已经标识了每个顶点与其近邻的连接，这意味着使用使用选定顶点作为搜索数据的值的列表理解很容易找到第一组邻居。我实际上想重复这个寻找每一个邻居，但以最有效的方法。为了实现这一点，正在搜索的数据(我已经计算过了)在下面的代码中被指定为p_2，其形式是：(源坐标、邻域坐标)，而Coordinates_xyz是网络唯一顶点的列表。下面的代码演示了我目前如何只识别第一个邻居。

再说一遍，我已经有了所有的邻居数据，我只需要最好的方法来搜索这些数据来查找到每个顶点的连接。

清晰度：

我想做的事情的例子：

我的程序生成的一种类型的数据代表了一个重复正方形模式的顶点网络。每个顶点(远离边缘)有4个邻居，然后每个邻居有4个邻居(尽管这些邻居的一个邻居是前一个顶点，因此是折扣的)等等。如果我选择坐标为(x20, y20, z20)的顶点20并在p_2中搜索邻居，它可能会返回(例如)：

(原产地)，(邻居)

(x20, y20, z20), (x21, y21, z21)

(x23, y23, z23), (x20, y20, z20)

(x26, y26, z23), (x20, y20, z20)

(x20, y20, z20), (x30, y30, z30)

然后我可以清楚地看到，顶点21、23、26和30是顶点20的邻接点，但我需要分别重复对21、23、26和30的搜索过程，才能找到第二近邻。对于N个最近的邻居，我必须找到一种有效(尽可能)的方法来重复对每个邻居的搜索，并从顶点20向外移动，同时跟踪邻居的顺序。同样，我知道这会对大N产生影响，但是它通常不会在N>4上运行，下面的代码解决了N= 1的问题。

matching_1_NN_list=[]
matching_1_NN_list[:]=[]    
for vertex in xrange(len(Coordinates_xyz)):
    #Target vertex Coordinates_xyz[vertex] 
    matching_1_NN = [x for x in p_2 if Coordinates_xyz[vertex] in x]
    matching_1_NN_Component_0=column(matching_1_NN, 0)
    matching_1_NN_Component_1=column(matching_1_NN, 1)
    for x in matching_1_NN_Component_0:
        if x == Coordinates_xyz_final[vertex]:
            pass
        else:
            x=x, vertex, 1 #coordinates, vertex number, order (1 = first neighbour)
            matching_1_NN_list.append(x)


    for x in matching_1_NN_Component_1:
        if x == Coordinates_xyz_final[vertex]:
            pass
        else:
            x=x, vertex, 1
            matching_1_NN_list.append(x)
    matching_1_NN_list=set(list(matching_1_NN_list)) #Removes Duplicates

Answer 1

这似乎在很大程度上改善了你寻找邻居的方式。在当前的方法中，您循环遍历整个对列表，并在每次需要查找顶点的邻居时进行大量的成员资格检查。最好只执行这个步骤一次，并在字典中查找结果。例如，如果有以下顶点：

 7 |  E
 6 |
 5 |
 4 |  D
 3 |
 2 |     B  C
 1 |  A
 0 +----------
   0  1  2  3

最近的邻居名单如下：

p_2 = [('A', 'B'),
       ('B', 'C'),
       ('C', 'B'),
       ('D', 'B'),
       ('E', 'D')]

你可以这样做，例如：

from collections import defaultdict

p_2_dict = defaultdict(set)
for a, b in p_2:
    p_2_dict[a].add(b)
    p_2_dict[b].add(a)

def find_neigbours(start_vertex, levels):
    found = []
    from_vertices = [start_vertex]
    for i in range(1, levels+1):
        new_from_vertices = []
        for vertex in from_vertices:
            for neighbour in p_2_dict[vertex]:
                new_from_vertices.append(neighbour)
                found.append( (neighbour, i) )
        from_vertices = new_from_vertices
    return found

然而，这发现了很多重复的东西。正如您在示例代码中所做的那样，您可以使用集合只存储唯一的值。此外，如果遇到开始顶点，您可以跳过它。

def find_neigbours(start_vertex, levels):
    found = set()
    from_vertices = [start_vertex]
    for i in range(1, levels+1):
        new_from_vertices = set()
        for vertex in from_vertices:
            for neighbour in p_2_dict[vertex]:
                if neighbour == start_vertex:
                    continue
                new_from_vertices.add(neighbour)
                found.add( (neighbour, i) )
        from_vertices = new_from_vertices
    return found

尽管如此，如果与其关联的“邻接点的顺序”与已存储的顺序不同，则存储重复的顶点。你想拿这些做什么？只存储当您第一次遇到特定顶点时的顺序？

输出：

In [49]: find_neigbours('A', 1)
Out[49]: set([('B', 1)])

In [50]: find_neigbours('A', 2)
Out[50]: set([('B', 1), ('D', 2), ('C', 2)])

# 'B' encountered with different order:
In [51]: find_neigbours('A', 3)
Out[51]: set([('B', 1), ('D', 2), ('B', 3), ('E', 3), ('C', 2)])