Python中从图形中删除重复的边

Question

我的程序返回一个元组列表，这些元组表示一个图的边，形式如下：

[(i, (e, 130)), (e, (i, 130)), (g, (a, 65)), (g, (d, 15)), (a, (g, 65))]

所以，（i，（e，130））意味着“i”与“e”相连，距离为130个单位。在

类似地，（e，（i，130））意味着“e”与“i”相连，距离为130个单位。 所以本质上，这两个元组代表同一件事。在

我如何从这个列表中删除它们中的任何一个？ 期望输出：

^{pr2}$

我试着写一个相等的函数。这有什么帮助吗？在

def edge_equal(edge_tuple1, edge_tuple2):
    return edge_tuple1[0] == edge_tuple2[1][0] and edge_tuple2[0] == edge_tuple1[1][0]

Answer 1

编写的最简单的解决方案是简单地迭代器并检查它们的相等性：

def edge_equal(edge_tuple1, edge_tuple2):
        return edge_tuple1[0] == edge_tuple2[1][0] and edge_tuple2[0] == edge_t\
uple1[1][0]

new = []

for i in range(len(graph)):
    found_equal = False
    for e in range(i,len(graph)):
        if edge_equal(graph[i],graph[e]):
            found_equal = True
            break
    if not found_equal:
        new.append(graph[i])

print new

Answer 2

如果一个元组(n1, (n2, distance))表示一个双向连接，我将引入一个规范化属性，它约束元组中两个节点的顺序。这样，每个可能的边都有一个唯一的表示。在

因此，归一化函数会将给定的（可能是未规范化的）边映射到规范化变量。然后可以使用此函数对所有给定的边进行规格化。现在可以用几种方法消除重复。例如，将列表转换为集合。在

def normalize(edge):
    n1, (n2, dist) = edge
    if n1 > n2: # use a custom compare function if desired
        n1, n2 = n2, n1
    return (n1, (n2, dist))

edges = [('i', ('e', 130)), ('e', ('i', 130)), ('g', ('a', 65)), ('g', ('d', 15)), ('a', ('g', 65))]

unique_edges = set(map(normalize, edges))

# set([('e', ('i', 130)), ('d', ('g', 15)), ('a', ('g', 65))])

Answer 3

重建每个边以获得其替代形式，并检查替代形式是否已在新集中。如果没有，则添加到集合中：

lst = [('i', ('e', 130)), ('e', ('i', 130)), ('g', ('a', 65)), ('g', ('d', 15)), ('a', ('g', 65))]

r = set()
for e, v in lst:
    if (v[0], (e, v[1])) in r:
        continue
    r.add((e, v))

print(list(r))
# [('i', ('e', 130)), ('g', ('a', 65)), ('g', ('d', 15))]