I am trying to solve an exam timetabling problem using graph colouring from the networkx library. I've taken the source code for the DSatur and the colouring algorithm and I'm trying to modify it for my specific requirements. I've made a graph with the exams as the nodes and if any two exams have even one student in common, they have an edge between them. The algorithm colours the graph with the fewest colours possible, but I need at least 512 colours (since there are 512 exam slots) to be used. I tried using equitable colouring and that works pretty well, but I would prefer using the DSatur algorithm since it schedules the exams with the highest degrees first. I'm confused as to how I can set the number of colours to 512. The highest degree for the graph is 203, which means it shouldn't be a problem.
My code for the colouring and DSatur heuristic are as follows:
def coloring_algorithm(G):
if len(G) == 0:
return {}
colors = {}
nodes = DSatur(G, colors) #DSatur gives order of nodes
for u in nodes:
neighbour_colors = {colors[v] for v in G[u] if v in colors}
for color in itertools.count():
if color not in neighbour_colors:
break
colors[u] = color
return colors
def DSatur(G, colors): #ADD PRIORITY QUEUE HERE
distinct_colors = {v: set() for v in G}
for i in range(len(G)):
if i == 0:
node = max(G, key=G.degree)
yield node
for v in G[node]:
distinct_colors[v].add(0)
else:
saturation = {
v: len(c) for v, c in distinct_colors.items() if v not in colors
}
node = max(saturation, key=lambda v: (saturation[v], G.degree(v)))
yield node
color = colors[node]
for v in G[node]:
distinct_colors[v].add(color)