连接具有公共点的线

Question

我有一个这样的行列表：

Lines = ['1', '2', '3', '4', '5', '6', '7', '8']

每条线有两个点 I 和 J：

LinesDetail = {
    '1': {
        'I': '100',
        'J': '101'},
    '2': {
        'I': '101',
        'J': '102'},
    '3': {
        'I': '256',
        'J': '257'},
    '4': {
        'I': '257',
        'J': '258'},
    '5': {
        'I': '258',
        'J': '259'},
    '6': {
        'I': '304',
        'J': '305'},
    '7': {
        'I': '305',
        'J': '306'},
    '8': {
        'I': '102',
        'J': '103'}}

正如您在图片中看到的，其中一些线具有相互点，因此它们相互连接，我需要知道哪些线相互连接。

我尝试了 while 循环，但我不知道如何解决此类问题的基本概念。

结果是：

result = [["1","2","8"],["3","4","5"],["6","7"]]

所有线都是垂直的

Answer 1

这是一个寻找连通分量的图问题。一种可能的解释是，外部键是标签，内部字典是边（内部字典值是节点）。如果依赖性不是问题，Python 有一个很好的 APInetworkx来处理图形。具体来说，可以使用 UnionFind 数据结构来查找不相交子集。

from networkx.utils.union_find import UnionFind

# reverse the label-edge mapping to get a mapping from nodes to edge labels
edges = {}
for k, d in LinesDetail.items():
    for v in d.values():
        edges.setdefault(v, []).append(k)

# construct union-find data structure
c = UnionFind()
for lst in edges.values():
    c.union(*lst)

# get the disjoint sets as sorted lists
result = list(map(sorted, c.to_sets()))
result
# [['1', '2', '8'], ['3', '4', '5'], ['6', '7']]