November 13, 2022
Data Structures & Algorithms
Introduction
This generator class provides methods for creating various graphs, including Erdos-Renyi random graphs, random bipartite graphs, random k-regular graphs, and random rooted trees.
There is also a dependency on the Undirected Graphs class.
Functions
simple
Returns a random simple graph containing V vertices and E edges.
simple_erdos_renyi
Returns a random simple graph on V vertices, with an edge between any two vertices with probability p. This is sometimes referred to as the Erdos-Renyi random graph model.
complete
Returns the complete graph on V vertices.
bipartite
Returns a random simple bipartite graph on V1C and V2C vertices with E edges.
bipartite_erdos_renyi
Returns a random simple bipartite graph on V1C and V2C vertices, containing each possible edge with probability p.
complete_bipartite
Returns a complete bipartite graph on V1C and V2C vertices.
path
Returns a path graph on V vertices.
complete_binary_tree
Returns a complete binary tree graph on V vertices.
cycle
Returns a cycle graph on V vertices.
eulerian_cycle
Returns an Eulerian cycle graph on V vertices.
eulerian_path
Returns an Eulerian path graph on V vertices.
wheel
Returns a wheel graph on V vertices, a single vertex connected to every vertex in a cycle on V-1 vertices.
star
Returns a star graph on V vertices, a single vertex connected to every other vertex.
k_regular
Returns a uniformly random k-regular graph on V vertices (not necessarily simple).
tree
Returns a uniformly random tree on V vertices. This algorithm uses a Prufer sequence and takes time proportional to VlogV.
Class Implementation
class GraphGenerator:
def __init__(self):
pass
class _Edge:
def __init__(self, v1, v2):
self.__v1 = min(v1, v2)
self.__v2 = max(v1, v2)
def __str__(self):
return str(self.__v1) + "-" + str(self.__v2)
def __hash__(self):
return hash((self.__v1, self.__v2))
def __eq__(self, other):
return self.__v1 == other.__v1 and self.__v2 == other.__v2
def simple(self, V, E):
from random import randrange
assert(E >= 0)
assert(2 * E <= (V * (V - 1)))
g = Graph(V)
edges = set()
while g.E() < E:
v1 = randrange(V)
v2 = randrange(V)
if v1 != v2:
edge = self._Edge(v1, v2)
if edge not in edges:
edges.add(edge)
g.add_edge(v1, v2)
return g
def simple_erdos_renyi(self, V, p):
assert(p >= 0.0 and p <= 1.0)
from random import uniform
g = Graph(V)
for v1 in range(V):
for v2 in range(v1 + 1, V):
if uniform(0, 1) < p:
g.add_edge(v1, v2)
return g
def complete(self, V):
return self.simple_erdos_renyi(V, 1.0)
def bipartite(self, V1C, V2C, E):
from random import randrange, shuffle
assert(E >= 0)
assert(E <= (V1C * V2C))
V = V1C + V2C
g = Graph(V)
vertices = [i for i in range(V)]
shuffle(vertices)
edges = set()
while g.E() < E:
i = randrange(V1C)
j = V1C + randrange(V2C)
edge = self._Edge(vertices[i], vertices[j])
if edge not in edges:
edges.add(edge)
g.add_edge(vertices[i], vertices[j])
return g
def bipartite_erdos_renyi(self, V1C, V2C, p):
assert(p >= 0.0 and p <= 1.0)
from random import uniform, shuffle
V = V1C + V2C
g = Graph(V)
vertices = [i for i in range(V)]
shuffle(vertices)
for i in range(V1C):
for j in range(V2C):
if uniform(0, 1) < p:
g.add_edge(vertices[i], vertices[V1C + j])
return g
def complete_bipartite(self, V1C, V2C):
return self.bipartite_erdos_renyi(V1C, V2C, 1.0)
def path(self, V):
from random import shuffle
g = Graph(V)
vertices = [i for i in range(V)]
shuffle(vertices)
for i in range(V - 1):
g.add_edge(vertices[i], vertices[i + 1])
return g
def complete_binary_tree(self, V):
from random import shuffle
g = Graph(V)
vertices = [i for i in range(V)]
shuffle(vertices)
for i in range(1, V):
g.add_edge(vertices[i], vertices[(i - 1) // 2])
return g
def cycle(self, V):
from random import shuffle
g = Graph(V)
vertices = [i for i in range(V)]
shuffle(vertices)
for i in range(V - 1):
g.add_edge(vertices[i], vertices[i + 1])
g.add_edge(vertices[V - 1], vertices[0])
return g
def eulerian_cycle(self, V, E):
assert(E > 0)
assert(V > 0)
from random import randrange
g = Graph(V)
vertices = [randrange(V) for i in range(E)]
for i in range(E - 1):
g.add_edge(vertices[i], vertices[i + 1])
g.add_edge(vertices[E - 1], vertices[0])
return g
def eulerian_path(self, V, E):
assert(E >= 0)
assert(V > 0)
from random import randrange
g = Graph(V)
vertices = [randrange(V) for i in range(E + 1)]
for i in range(E):
g.add_edge(vertices[i], vertices[i + 1])
return g
def wheel(self, V):
assert(V > 1)
from random import shuffle
g = Graph(V)
vertices = [i for i in range(V)]
shuffle(vertices)
for i in range(1, V - 1):
g.add_edge(vertices[i], vertices[i + 1])
for i in range(1, V):
g.add_edge(vertices[0], vertices[i])
return g
def star(self, V):
assert(V > 0)
from random import shuffle
g = Graph(V)
vertices = [i for i in range(V)]
shuffle(vertices)
for i in range(1, V):
g.add_edge(vertices[0], vertices[i])
return g
def k_regular(self, V, k):
assert((V * k) % 2 == 0)
from random import shuffle
g = Graph(V)
vertices = [0 for _ in range(V * k)]
for v in range(V):
for j in range(k):
vertices[v + V * j] = v
shuffle(vertices)
for i in range((V * k) // 2):
g.add_edge(vertices[2 * i], vertices[2 * i + 1])
return g
# G.addEdge(pq.delMin(), pq.delMin());
def tree(self, V):
assert(V > 0)
from random import randrange
g = Graph(V)
if V > 1:
prufer = [randrange(V) for i in range(V - 2)]
degree = [1 for i in range(V)]
for i in range(V - 2):
degree[prufer[i]] += 1
from queue import PriorityQueue
pq = PriorityQueue()
for v in range(V):
if degree[v] == 1:
pq.put(v)
for i in range(V - 2):
v = pq.get()
g.add_edge(v, prufer[i])
degree[v] -= 1
degree[prufer[i]] -= 1
if degree[prufer[i]] == 1:
pq.put(prufer[i])
g.add_edge(pq.get(), pq.get())
return gGenerator Usage Samples
def test_graph_generator():
V = 11
E = 20
V1C = V // 2
V2C = V - V1C
gg = GraphGenerator()
print('COMPLETE GRAPH')
g = gg.complete(V)
print(g)
print('SIMPLE GRAPH')
g = gg.simple(V, E)
print(g)
print('SIMPLE GRAPH (ERDOS RENYI)')
p = 2. * E / (V * (V - 1))
g = gg.simple_erdos_renyi(V, p)
print(g)
print('COMPLETE BIPARTITE GRAPH')
g = gg.complete_bipartite(V1C, V2C)
print(g)
print('BIPARTITE GRAPH')
g = gg.bipartite(V1C, V2C, E)
print(g)
print('BIPARTITE GRAPH (ERDOS RENYI)')
p = 1. * E / (V1C * V2C)
g = gg.bipartite_erdos_renyi(V1C, V2C, p)
print(g)
print('PATH GRAPH')
g = gg.path(V)
print(g)
print('CYCLE GRAPH')
g = gg.cycle(V)
print(g)
print('COMPLETE BINARY TREE')
g = gg.complete_binary_tree(V)
print(g)
print('EULERIAN CYCLE')
g = gg.eulerian_cycle(V, E)
print(g)
print('EULERIAN PATH')
g = gg.eulerian_path(V, E)
print(g)
print('WHEEL GRAPH')
g = gg.wheel(V)
print(g)
print('STAR GRAPH')
g = gg.star(V)
print(g)
print('4-REGULAR GRAPH')
g = gg.k_regular(V, 4)
print(g)
print('TREE')
g = gg.tree(V)
print(g)
