Skip to content

Instantly share code, notes, and snippets.

@SimonBerens
Last active March 7, 2023 01:45
Show Gist options
  • Save SimonBerens/174f74338d6a6a713fa414cb9673174b to your computer and use it in GitHub Desktop.
Save SimonBerens/174f74338d6a6a713fa414cb9673174b to your computer and use it in GitHub Desktop.
Generate dense and sparse graphs graphs with a defined number of vertices and edges
import random
import math
def random_pick(n, m):
"""Pick m integers from a bag of the integers in [0, n) without replacement"""
d = {i : i for i in range(m)} # For now, just pick the first m integers
res = []
for i in range(m): # Pick the i-th number
j = random.randrange(i, n)
# Pick whatever is in the j-th slot. If there is nothing, then pick j.
if j not in d:
d[j] = j
d[i], d[j] = d[j], d[i] # Swap the contents of the i-th and j-th slot
res.append(d[i])
return res
def gen_random_graph(V, E):
"""Generate an undirected graph in the form of an adjacency list with no duplicate edges or self loops"""
g = [[] for _ in range(V)]
edges = random_pick(math.comb(V, 2), E) # Pick E integers that represent the edges
for e in edges: # Decode the edges into their vertices
u = int((1 + math.sqrt(1 + 8 * e)) / 2)
v = e - math.comb(u, 2)
g[u].append(v)
g[v].append(u)
return g
# The complete graph on 4 vertices
print(gen_random_graph(4, 6)) # [[3, 2, 1], [3, 2, 0], [1, 0, 3], [0, 1, 2]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment