Как выбрать грани случайно на моем графике?

Я хочу случайным образом извлекать множество ребер из графика. Я могу сделать это:

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

Но это неэффективно. Удалить вершины графа - тяжелая операция.

Кто-нибудь знает эффективный способ без удаления вершин графа?

2 ответа

Это должно работать, но может возвращать меньше, чем 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


Это может быть дорогостоящим для итерации по краям, поскольку может быть гораздо больше ребер, чем вершин (| V | * (| V | -1)/2).

Эта проблема эквивалентна выбору 2n случайных вершин, которые связаны парами. Он может быть реализован путем сохранения набора уже выбранных вершин и случайного выбора следующей вершины, а также над ней, которые еще не выбраны.

Алгоритм, описанный, является жадным. Существует верхняя граница для n, которая задается максимальным совпадением. В случае, если n близок к максимальной согласованной мощности, верхний алгоритм может выйти из строя. В этом случае должен использоваться стандартный алгоритм сопоставления.

licensed under cc by-sa 3.0 with attribution.