在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个单位。因此，这两个元组本质上表示相同的事情。

我如何从该列表中删除其中任何一个？

期望输出：

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

我尝试编写一个相等性函数。这会有所帮助吗？

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

- Abhishek Tumuluru

Answer 1

如果一个元组 (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))])

- Michael Hoff

---

这正是我所需要的！非常感谢 :) - Abhishek Tumuluru

Answer 2

重构每个边缘以采用其备选形式，并检查备选形式是否已在新集合中。如果没有，则将其添加到集合中：

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))]

- Moses Koledoye

---

另一种非常好的方法！感谢您的回答 :) - Abhishek Tumuluru

Answer 3

最简单的解决方案是迭代并检查它们是否相等：

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

- James

---

我之前尝试过非常类似的方法。现在我知道自己哪里出错了！非常感谢您的回复！ - Abhishek Tumuluru

这个解决方案需要二次检查（O(N^2)）的双重循环。使用集合会更加高效，就像Michael Hoff和Moses Kaledoye提供的其他两个答案一样。 - alexis

是的，我明白了。我更喜欢使用list(set())而不是两个for循环。谢谢！ - Abhishek Tumuluru

Answer 4

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

for each in edges:
    try:
        edges.remove((each[1][0], (each[0], each[1][1])))
    except ValueError:
        pass

在遍历时将向量反转并移除

- be_good_do_good

---

糟糕，我本可以像这样反转它们。谢谢！ - Abhishek Tumuluru