如何通过共同元素对连音数组进行分组？

Question

我有一系列段，定义为两个连音（两个顶点）的数组。 每个线段可以与另一个线段共享一个顶点，并且线段的组合可能会形成一个或多个闭环。

为了找到闭环，我当前的方法是找到哪些线是相连的（共享一个顶点）并在按顺时针顺序排列每个组之前将它们分组。

我们看下面的例子（用Python编写）

lines = {
    "A": [(0, 0), (0, 1)],  # A,B -- B,C
    "B": [(0, 1), (1, 1)],  # |       |
    "C": [(1, 1), (1, 0)],  # |       |
    "D": [(1, 0), (0, 0)],  # A,D -- C,D
    
    "E": [(4, 4), (4, 5)],  # E,F - F,G
    "F": [(4, 5), (5, 5)],  # |   /
    "G": [(5, 5), (4, 4)],  # E,G
}

answer = ["ABCD", "EFG"]

对共享顶点（连元组值）的条目进行分组（使用标准 Python 库）的最佳方法是什么？ 不保证字典中各行的顺序，但此处按顺时针顺序排列，以便于阅读。

我尝试了一种简单的循环方法（图论）来解决这个问题，但是返回的循环包含的内容比我想要的使用上面示例中的顶点要多得多，所以我重新审视了我解决问题的方法，这导致我提出这个问题。

Answer 1

这可以通过诸如

networkx

之类的图形库来实现。您可以使用

connected components

或

simple_cycles

，具体取决于确切的预期逻辑：

import networkx as nx
from itertools import pairwise

G = nx.from_edgelist(lines.values(), create_using=nx.DiGraph)

names = {tuple(v):k for k,v in lines.items()}
# {((0, 0), (0, 1)): 'A',
#  ((0, 1), (1, 1)): 'B',
#  ((1, 1), (1, 0)): 'C',
#  ((1, 0), (0, 0)): 'D',
#  ((4, 4), (4, 5)): 'E',
#  ((4, 5), (5, 5)): 'F',
#  ((5, 5), (4, 4)): 'G'}

# connected components
cc = [[names[e] for e in G.subgraph(c).edges() if e in names]
      for c in nx.weakly_connected_components(G)]
# [['A', 'B', 'C', 'D'], ['E', 'F', 'G']]

# cycles
cy = [[names[(c[-1], c[0])]]+[names[e] for e in pairwise(c)]
      for c in nx.simple_cycles(G)]
# [['G', 'E', 'F'], ['A', 'B', 'C', 'D']]

图表：