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

Question

我有一个二维 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]]]

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

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

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

我想形成两个图形，每个方格一个。为此，我使用了一个 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, ...)，值是边列表

行的一点解释

graph_number = vertices.get(v1) or vertices.get(v2) or next(graph_numbers)

该行大致等于：

number1 = vertices.get(v1)
number2 = vertices.get(v2)
if number1 is None and number2 is None:
    graph_number = next(graph_numbers)
elif number1 is not None:
    graph_number = number1
else:
    graph_number = number2

表示：如果 v1 和 v2 都不在顶点中，则生成一个新数字（即 next(graph_numbers)）。否则，将 graph_number 分配给不是 None 的任何值。

不仅那一行很简洁，它还利用了Python的短路特性：解释器首先计算vertices.get(v1)。如果这个 return 是一个数字 (1, 2, ...) 那么解释器将 return 这个数字并跳过计算 vertices.get(v2) or next(graph_numbers) 部分。

如果vertices.get(v1) returns None，也就是Python中的False，那么解释器会计算[=23]的下一段=]：vertices.get(v2)。同样，如果此 return 是一个非零数字，则计算停止并且该数字为 return。如果 vertices.get(v2) returns None，则解释器计算最后一段，next(graph_numbers) 和 returns 那个值。

Answer 2

我建议对图进行 'diffusion-like' 处理以找到不相交的子图。想到的一种算法是breadth-first search；它通过查找可以从起始节点到达哪些节点来工作。

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]]] 

# edge list usually reads v1 -> v2
graph = {}
# however these are lines so symmetry is assumed
for l in linelist:
    v1, v2 = map(tuple, l)
    graph[v1] = graph.get(v1, ()) + (v2,)      
    graph[v2] = graph.get(v2, ()) + (v1,)

def BFS(graph):
    """
    Implement breadth-first search
    """
    # get nodes
    nodes = list(graph.keys())
    graphs = []
    # check all nodes 
    while nodes:
        # initialize BFS
        toCheck = [nodes[0]]
        discovered = []
        # run bfs
        while toCheck:
            startNode = toCheck.pop()
            for neighbor in graph.get(startNode):
                if neighbor not in discovered:
                    discovered.append(neighbor)
                    toCheck.append(neighbor)
                    nodes.remove(neighbor)
        # add discovered graphs
        graphs.append(discovered)
    return graphs
print(BFS(graph))
for idx, graph in enumerate(BFS(graph)):
    print(f"This is {idx} graph with nodes {graph}")

输出

This is 0 graph with nodes [(1, 0), (0, 1), (0, 0), (1, 1)]
This is 1 graph with nodes [(3, 1), (2, 2), (1, 2), (3, 2)]

您可能对用于分析图表的包 networkx 感兴趣。例如，找到不相交的子图非常简单：

import networkx as nx
tmp = [tuple(tuple(j) for j in i) for i in linelist]
graph = nx.Graph(tmp);
for idx, graph in enumerate(nx.connected_components(graph)):
    print(idx, graph)

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

Accessing items in a list, and forming graphs

python

graph

image-segmentation

输出