I need to generate an adjacency list for a random directed graph with a number of nodes n
and a number of edges m
. I have found this question, which is similar, but the edges exist or not based on probability.
CodePudding user response:
You can use a similar algorithm as in @kaya3's answer on the question you linked to. Instead of taking a probability p
, take the number of edges m
, and instead of iterating all possible edges, take a sample
of it of size m
. Make those edges unconditionally.
The original code allowed loops to be generated (a node having an edge to itself) when directed
. As you briefly commented you didn't want to have such loops, I added the corresponding if
condition:
from random import sample
from itertools import product, combinations
def random_graph(n, m, *, directed=False):
nodes = range(n)
adj_list = [[] for i in nodes]
possible_edges = product(nodes, repeat=2) if directed else combinations(nodes, 2)
for u, v in sample(list(possible_edges), m):
if u != v: # added
adj_list[u].append(v)
if not directed:
adj_list[v].append(u)
return adj_list