访问列表中的项目，并形成图表

Question

我有一个2D numpy数组的列表：

linelist = [[[0,0],[1,0]],[[0,0],[0,1]],[[1,0],[1,1]],[[0,1],[1,1]],[[1,2],[3,1]],[[1,2],[2,2]],[[3,1],[3,2]],[[2,2],[3,2]]]

线表中的每一行都是连接边的顶点阵列。这些元素是形成两个正方形的线：

-----
|   |
-----

    -----
    |   |
    -----

我想形成两个图形，每个正方形一个。为此，我使用一个for循环。如果图中没有两个顶点，则我们形成一个新图。如果线列表中存在一个顶点，则将其添加到当前图形中。为了连接两条线，它们需要共享一个顶点。但是，我在编码时遇到了麻烦。这是我到目前为止的内容：

    graphs = [[]]
    i=0
    for elements in linelist:
        for graph in graphs:
            if elements[0] not in graph[i] and elements[1] not in graph[i]:
                graphs.append([])
                graphs[i].append(elements)
                i=i+1
            else:
                graphs[i].append(elements)

Answer 1

我的方法涉及2次遍历列表。在第一遍中，我将查看顶点并为每个顶点分配一个图形编号（1、2，...）。如果两个顶点都没有出现，我将分配一个新的图形编号。否则，将其分配给现有的一个。

[在第二遍中，我遍历列表并将属于同一图形编号的边归为一组。这是代码：

import collections
import itertools
import pprint


linelist = [[[0,0],[1,0]],[[0,0],[0,1]],[[1,0],[1,1]],[[0,1],[1,1]],[[1,2],[3,1]],[[1,2],[2,2]],[[3,1],[3,2]],[[2,2],[3,2]]]


# First pass: Look at the vertices and figure out which graph they
# belong to
vertices = {}
graph_numbers = itertools.count(1)
for v1, v2 in linelist:
    v1 = tuple(v1)
    v2 = tuple(v2)
    graph_number = vertices.get(v1) or vertices.get(v2) or next(graph_numbers)
    vertices[v1] = graph_number
    vertices[v2] = graph_number

print('Vertices:')
pprint.pprint(vertices)


# Second pass: Sort edges
graphs = collections.defaultdict(list)
for v1, v2 in linelist:
    graph_number = vertices[tuple(v1)]
    graphs[graph_number].append([v1, v2])

print('Graphs:')
pprint.pprint(graphs)

输出：

Vertices:
{(0, 0): 1,
 (0, 1): 1,
 (1, 0): 1,
 (1, 1): 1,
 (1, 2): 2,
 (2, 2): 2,
 (3, 1): 2,
 (3, 2): 2}
Graphs:
defaultdict(<type 'list'>, {1: [[[0, 0], [1, 0]], [[0, 0], [0, 1]], [[1, 0], [1, 1]], [[0, 1], [1, 1]]], 2: [[[1, 2], [3, 1]], [[1, 2], [2, 2]], [[3, 1], [3, 2]], [[2, 2], [3, 2]]]})

注意

• 我必须将每个顶点从列表转换为元组，因为列表不能成为字典的键。
• [graphs的行为就像字典，键是图形编号（1、2，...），值是边列表