传递归约 - 代码错误 - Python

Question

所以我正在尝试编写代码来对无环图进行传递归约。所以元素是：

(3, 5), (5, 2), (2, 1), (4, 2), (3, 1), (4, 1)

这是我到目前为止写的：

graph = [[3, 5],[5, 2],[2, 1],[4, 2],[3, 1],[4, 1]]

for i in range(len(graph)):
    for j in range(len(graph)):
        for k in range(len(graph)):
            if [i,j] in graph and [j,k] in graph:
                a = [i,k]
                graph.pop(a)
print(graph)

在运行之后，我希望在删除 (4,1) 后得到以下内容：

>> (3, 5), (5, 2), (2, 1), (4, 2), (3, 1)

而是 returns:

>> (3, 5), (5, 2), (2, 1), (4, 2), (3, 1), (4, 1)

我不知道我做错了什么。如果有人能指出错误就太好了！

P.S：传递归约是去除图的冗余边。例如：

if ( A -> B ) and ( B -> C ), then ( A -> C ),换句话说：如果A连接到B并且B连接到C，那么A也连接到C。在这种情况下 ( A -> C ) 是多余的，因为 A 可以通过 B 到达 C 因此应该删除。

Answer 1

我改进了你的代码，我添加了一个条件 if a in graph: 因为在某些情况下会出现传递归约并且元素 [i,k] 不存在。此外，函数 pop() 通过索引删除元素，而不是像 remove().

这样的对象

graph = [[3, 5],[5, 2],[2, 1],[4, 2],[3, 1],[4, 1]]

for i in range(len(graph)):
    for j in range(len(graph)):
        for k in range(len(graph)):
            if [i,j] in graph and [j,k] in graph:
                a = [i,k]
                if a in graph:
                    graph.remove(a)
print(graph)

希望对您有所帮助

传递归约 - 代码错误 - Python

Transitive reduction - Error with code - Python

python

graph-theory

list

transitive-closure