python - 查找表示为列表的边

Question

假设我们有一个二分图，其中的节点表示为列表。例如，假设二分图的节点为 l1 = [1,2,3,4,5] 和 l2 = [6,7,8,9,10] 是两个分区中的节点 边是 [[1,8, 'a'], [4,9,'b']] 表示为列表的列表，如图 1 所示

如果我们以某种方式合并了二分图的节点，现在表示为 1通过 [[1,2,3], [4, 5]] 和 [[6,7] , [8, 9, 10]] 然后在这个新的图，如果原始图中的任何对之间有边，我们就会在这些组之间有边。例如，在上面的例子中，[1,2,3] 和 [8,9,10] 之间会有一条 a 边> 由于最初在 1 和 8 之间有一条边，因此如图 1 所示.如何在 Python 中找到新图中的边，什么是合适的数据结构表示以及如何从这个原始图中找到生成的边？

我为此使用了列表，但问题是要找到这些边，我必须遍历新图中的所有节点以检查是否应该有边。有没有更有效的方法来做到这一点？

我试过的代码:

l1 = [1,2,3,4,5]
l2 = [6,7,8,9,10]
l3 = [[1,2,3], [4, 5]]
l4 = [[6,7] , [8, 9, 10]]
edges = [[1,8, 'a'], [4,9,'b']]

for e in edges:
    for l in l3:
        for k in l4:
            if e[0] in l and e[1] in k:
                print(e[0], e[1], e[2])

Answer 1

让我们从获取包含特定值的组的索引开始。

def idx_group_in_list(value, list_) -> int:
    """e.g. value=2, list_=[[1,2],[3,4]] -> 0
    because the value 2 is in the first (idx=0) inner list"""
    for idx, l in enumerate(list_):
        if value in l:
            return idx
    return -1

在下文中，我将使用基于字典的解决方案。这使得检查边是否已经存在变得更加容易。

l3 = [[1, 2, 3], [4, 5]]
l4 = [[6, 7], [8, 9, 10]]
edges = [[1, 8, 'a'], [4, 9, 'b']]

new_edges = {}
for e in edges:
    # left
    l_idx = idx_group_in_list(e[0], l3)
    r_idx = idx_group_in_list(e[1], l4)
    if (l_idx, r_idx) in new_edges:
        pass    # two edges are squeezed. Maybe add some special stuff here
    new_edges[(l_idx, r_idx)] = e[2]

print(new_edges)
expected_output = {(0, 1): 'a', (1, 1): 'b'}
print(expected_output == new_edges)

编辑:

我做了一些非常简单的性能测试。大多数代码保持不变，我只是改变了方式，生成了列表。

num_nodes_per_side = 1000
left = [[i] for i in range(num_nodes_per_side)]
right = [[i] for i in range(num_nodes_per_side, num_nodes_per_side*2)]
edges = [[i, j, 'a'] for i, j in zip(range(num_nodes_per_side), range(num_nodes_per_side, num_nodes_per_side*2))]

# result for num_nodes_per_side = 3
>>> left
[[0], [1], [2]]
>>> right
[[3], [4], [5]]
>>> edges
[[0, 3, 'a'], [1, 4, 'a'], [2, 5, 'a']]

这意味着每个左组都有一条边到右组。以下是我的 timeit 结果，基于 num_nodes_per_side。

• 10: 2.0693999999987778e-05
• 100: 0.0004394410000000404
• 1000: 0.042664883999999986
• 10000: 4.629786907