连接具有共同点的线

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'}}

如您在图片中所见，其中一些行有共同点 因此，它们相互连接，我需要知道哪些线相互连接。

我在循环时尝试过，但我没有解决此类问题的基本思想。

，结果是：

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

所有行都是垂直的

Answer 1

这是查找连接组件的图形问题。一个可能的解释是外键是标签，内部字典是边缘（内部dict值是节点）。如果依赖关系不是问题，则Python具有涉及图形的不错的API 。具体而言，可以使用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']]

Answer 2

这不是最佳的解决方案，而是将其放在那里以来，因为我一直在

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'}}
Lines = ['1', '2', '3', '4', '5', '6', '7', '8']

results = []
for item in Lines:
    match_this = LinesDetail[item]['J']
    list_form = []
    for key, value in LinesDetail.items():
        if match_this == value['I']:
            results.append([item, key])
needed_list = []                
for i in range(0, len(results)-1):    
    if results[i][1] == results[i+1][0]:

        yes_list = results[i][:1] + results[i+1]

        needed_list.append(yes_list)
    else:
        try:
            if results[i][1] == results[i+2][0]:
                continue
        except:
            needed_list.append(results[i+1])

        
print(needed_list)

输出它：

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