如何在圖形中隨機選擇邊緣？

我想從圖中隨機提取設定的邊。我可以這樣做：如何在圖形中隨機選擇邊緣？

import networkx as nx 
from random import sample 
g = nx.karate_club_graph() 
k=5 
print sample(g.edges(), k)

輸出

# [(0, 31), (15, 32), (31, 33), (8, 32), (4, 10)]

不過，我想每個頂點出現一次

例如：

(0, 31) and (31, 33) # --> incorrect

我嘗試這樣做：

result = [] 
while len(g.edges()): 
    edges = g.edges() 
    shuffle(edges) 
    result.append(edges[0]) 
    g.remove_nodes_from([edges[0][0],edges[0][1]])

但是，效果不佳。刪除圖形的頂點是一個沉重的操作。

任何人都知道一個有效的方法，而不刪除圖的頂點？

來源

2014-03-01 Alan Valejo

你應該保留一個散列表'L'（或任何其他數據結構）的頂點已被考慮。然後，如果'u'和'v'都不存在於'L'中，則只能追加邊緣'（u，v）'。這樣就不需要刪除節點。 –

你需要保證最低限度的設置嗎？即如果你是隨機的，你可以想出一個情況，對於一組節點A，B，C，D，A-> B，B-> C，C-> D。如果你隨機選擇A，你會得到兩條邊 - A-> B和C-> D。但是，如果先選擇B-> C，那麼A或D就沒有有效的邊界了。這是可以接受的嗎？ –

另外...老實說，在大多數情況下，igraph在處理邊時很痛苦，但實際上在這種情況下，我認爲邊緣序列對象會使這個處理更加直接，因爲它們是單獨索引的，但可以過濾。 –

這應該工作，但可能會返回小於n邊緣：

def get_rand_edges(g, n): 
    visited = set() 
    results = [] 
    edges = random.sample(g.edges(), n) 
    for edge in edges: 
     if edge[0] in visited or edge[1] in visited: 
      continue 
     results.append(edge) 
     if len(results) == n: 
      break 
     visited.update(edge) 
    return results

來源

2014-03-01 23:21:34 tmr232

它可以是昂貴的遍歷，邊，因爲可以比頂點更邊緣（| V | *（| V | -1）/ 2）。

此問題相當於選擇2n個成對連接的隨機頂點。它可以通過存儲一組已經選擇的頂點並隨機選擇下一個頂點和它尚未選擇的鄰點來實現。

描述的算法是貪婪的。 n有上限，由maximum matching給出。如果n接近最大匹配基數，則較高的算法可能會失敗。在這種情況下，必須使用標準匹配算法。

來源

2014-03-02 08:48:13 Ante

如何在圖形中隨機選擇邊緣？

回答

相關問題