Skip to content
Snippets Groups Projects
Select Git revision
  • b532041944a8315d76b40c7f918c222f327eb045
  • master default protected
2 results

in

Blame
    • main.py 2.99 KiB
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113 
    

    

    

    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")