How to choose edges randomly in my graph?

Question

I want to extract set edges randomly from a graph. I can do this:

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

output

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

However, I want each vertex appears one time

Eg.:

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

I tried this:

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

But, is ineffective. Remove vertices of the graph is a heavy operation.

Anyone know a efficient way without removing vertices of the graph?

Answer 1

This should work, but might return less than n edges:

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

Answer 2

It can be expensive to iterate through,edges, since there can be much more edges than vertices (|V|*(|V|-1)/2).

This problem is equivalent to choosing 2n random vertices which are connected in pairs. It can be implemented by storing set of already selected vertices and randomly selecting next vertex and it's nighbour that are not already selected.

Algorithm described is greedy. There is upper bound for n, which is given by maximum matching. In case that n is close to maximum matching cardinality, upper algorithm can fail. In that case standard matching algorithm has to be used.