# Random Graph & Tree Generator

Join me to stay up-to-date and get my new articles delivered to your inbox by subscribing here.

## 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:
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:
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:
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:
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):
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):
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):
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):
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):
for i in range(1, V):
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):
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

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()
degree[v] -= 1
degree[prufer[i]] -= 1
if degree[prufer[i]] == 1:
pq.put(prufer[i])
return g``````

## Generator 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)``````