The goal of this exercise is to provide a centralized implementation that simulates a randomized distributed algorithm. Your implementation should take a graph G = (V, E) with maximum degree \Delta as its input and simulate the following distributed randomized $(\Delta + 1)$-coloring algorithm until all vertices are colored:

Initially, all nodes are uncolored. Then, in synchronous iterations, each uncolored node selects a random candidate color from its list of available colors, that is, from the set of colors that none of its already permanently colored neighbors have. Then, nodes exchange their candidate colors with their neighbors. A node v that has a candidate color c that is not selected as a candidate color by any of its neighbors gets permanently colored with c, otherwise v discards its candidate color, remains uncolored, and proceeds with the next iteration.

The code may be written in any programming language. Submit your code via GIT (link the repository in your submission) including instructions on how to run it. Additionally provide several example inputs (on at least a few hundred nodes) and a test case that your algorithm computes a proper vertex coloring.

Run the program with the following statement:

$ python main.py <#nodes>

or run it with a graph that has 100 to 300 nodes:

$ python main.py

All the edges are generated with a random percentage chance between 0% and 100%.

Every execution the program checks if the algorithm ran correctly.