如何在图形中随机选择边缘？

我想从图中随机提取设定的边。我可以这样做：如何在图形中随机选择边缘？

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

如何在图形中随机选择边缘？

回答

相关问题