在Python列表中刪除從圖形重複的邊緣

我的程序返回的元組，其代表的曲線圖的邊的列表，在形式：在Python列表中刪除從圖形重複的邊緣

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

所以，（I，（E，130））意味着'我'連接到'e'並且距離130個單位。（e，（i，130））意味着'e'連接到'i'並且距離130個單位。所以基本上，這兩個元組代表了同樣的事情。

如何從列表中刪除它們中的任何一個？所需的輸出：

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

我試過寫一個equals函數。這會有幫助嗎？

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

來源

2016-07-24 Abhishek Tumuluru

如果元組(n1, (n2, distance))表示的雙向連接，我會引入規範化性質哪些約束在元組中的兩個節點的排序。這樣，每個可能的邊都有一個唯一的表示。

因此，歸一化函數會將給定的，可能未標準化的邊緣映射到歸一化變體。這個函數可以用來標準化所有給定的邊。重複現在可以通過幾種方法消除。例如，將列表轉換爲一個集合。

def normalize(t): 
    n1, (n2, dist) = t 
    if n1 < n2: # use a custom compare function if desired 
     return t 
    else: 
     return (n2, (n1, 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))])

歸一化函數也可配製這樣的（但僅在python < 3）：

def normalize((n1, (n2, dist))): 
    if n1 >= n2: 
     n1, n2 = n2, n1 
    return n1, (n2, dist)

來源

2016-07-24 18:41:32 mhoff

我喜歡這個解決方案..你有我的upvote ... :) –

這正是我需要的！非常感謝你:) –

重建每個邊緣採取其另一種形式，並檢查替換形式是已經在一個新的集合。如果沒有，那麼添加到該集合：

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

來源

2016-07-24 18:44:26

另一個真正偉大的方式來做到這一點！感謝您的回答:) –

最簡單的方法來寫會簡單地迭代器，並檢查所有的平等：

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

來源

2016-07-24 18:44:36 James

我嘗試過一種非常類似的方法。我看到我現在搞砸了！非常感謝您的回覆！ –

這是一個解決方案，需要雙循環的二次數檢查（'O（N^2）'）。與其他兩個答案（Michael Hoff和Moses Kaledoye）一樣，使用一組更有效率。 – alexis

是的，我想。我更喜歡list（set（））兩個for循環。謝謝！ –

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

扭轉載體和刪除他們當你遍歷

來源

2016-07-24 18:48:34

Darn，我可以像這樣扭轉它們。謝謝！ –

在Python列表中刪除從圖形重複的邊緣

回答

相關問題