传递减少 - 与代码错误 - Python

Question

所以我想写一个代码来做传递减少的Acyclic图。 所以元素是：

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

但相反，它返回：

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

我无法弄清楚我做错了什么。如果有人能指出错误，那会很棒！

P.S：Transtive reduction正在消除图形的冗余边缘。例如：如果（A→B）和（B→C），则（A→C），换句话说：如果A连接到B并且B连接到C，则A是也连接到C.在这种情况下， （A - > C）是多余的，因为A可以达到C到B，因此应该删除。

Answer 1

我改进了你的代码，我添加了一个条件if a in graph:，因为在某些情况下，Transtive减少出现并且元素[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)  

我希望这可以帮助你。