傳遞減少 - 與代碼錯誤 - 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)  

我希望這可以幫助你。