main.py

import random

class Graph:
	def __init__(self):
		self.vertices = []
		self.edges = []

	def __str__(self):
		return f"{{ Vertices: {len(self.vertices)} Edges: {len(self.edges)} }}"

class Vertex:
	def __init__(self):
		self.color = -1
		self.neighbours = []
		self.neighbours_candidates = []
		self.curr_candidate = -1

	def performRound(self, colors):
		if self.color != -1:
			return

		avail_colors = [*range(0, colors)]

		#print("Colors: ", colors)
		#print("Avail colors: ", avail_colors)
		#print("Avail colors len: ", len(avail_colors))
		
		self.neighbours_candidates = []

		#remove colors from neighbours that are colored
		for n in self.neighbours:
			if n.color != -1 and n.color in avail_colors:
				avail_colors.remove(n.color)

		self.curr_candidate = avail_colors[random.randrange(0, len(avail_colors))]

		#Exchange colors
		for n in self.neighbours:
			n.neighbours_candidates.append(self.curr_candidate)

	def afterRound(self):
		#We need this in a different function because the exchange colors would run parallel
		if not self.curr_candidate in self.neighbours_candidates:
			self.color = self.curr_candidate


def GetRandomGraph(degree, minVertex, maxVertex, minEdges, maxEdges):
	print(f"Generating random graph with degree {degree}, Vertices: {minVertex} - {maxVertex}, Edges: {minEdges} - {maxEdges}")
	G = Graph()
	vertexCount = random.randrange(minVertex, maxVertex)
	for i in range(vertexCount):
		G.vertices.append(Vertex())

	edgeCount = random.randrange(minEdges, maxEdges)

	for i in range(edgeCount):
		randVertex1 = G.vertices[random.randrange(0, len(G.vertices))]
		randVertex2 = G.vertices[random.randrange(0, len(G.vertices))]
		if randVertex1 != randVertex2 and len(randVertex1.neighbours) < degree and len(randVertex2.neighbours) < degree:
			G.edges.append((randVertex1, randVertex2))
			randVertex1.neighbours.append(randVertex2)
			randVertex2.neighbours.append(randVertex1)

	return G

def PerformAlgorithm(G, degree):
	colors = degree + 1

	round = 0
	collisions = CountColorCollisions(G)
	uncolored = CountUncolored(G)

	while(collisions > 0 or uncolored > 0):
		print(f"Starting round {round}. Collisions remaining: {collisions} Uncolored vertices: {uncolored}")
		for i in range(len(G.vertices)):
			G.vertices[i].performRound(colors)

		for i in range(len(G.vertices)):
			G.vertices[i].afterRound()

		collisions = CountColorCollisions(G)
		uncolored = CountUncolored(G)
		round += 1

def CountUncolored(G):
	count = 0
	for i in G.vertices:
		if i.color == -1:
			count += 1

	return count

def CountColorCollisions(G):
	collisions = 0
	for i in range(len(G.edges)):
		edge = G.edges[i]
		if(edge[0].color == edge[1].color):
			collisions += 1
	return collisions


degree = random.randrange(20, 50)
G = GetRandomGraph(degree, 1000, 3000, 2000, 5000)

print("Random Graph: ", str(G))

collisions = CountColorCollisions(G)

PerformAlgorithm(G, degree)

collisions = CountColorCollisions(G)
uncolored = CountUncolored(G)
print(f"After algorithm: Graph has {collisions} collisions and {uncolored} uncolored vertices")