Scamming the coding interview: Problem 004: Graph Coloring

graph_coloring.py

"""
Scamming the coding interview
"""

def color_graph(graph_adjacency, number_of_vertices):

    # First vertex gets the first color
    vertex_to_color_map = {
        0: 0
    }

    for i in range(1, number_of_vertices):

        neighbours = graph_adjacency[i]
        available_colors = [True for i in range(0, number_of_vertices)]

        for n in neighbours:
            color_of_neighbour = vertex_to_color_map.get(n)
            if color_of_neighbour is not None:
                available_colors[color_of_neighbour] = False

        # look for the first color that's available
        first_available_color = None
        for temp, color in enumerate(available_colors):
            if color:
                first_available_color = temp
                break

        if first_available_color is not None:
            vertex_to_color_map[i] = first_available_color

    return vertex_to_color_map


if __name__ == '__main__':

    graph_adjacency_list = {
        0: [1, 2],
        1: [0, 2, 3],
        2: [0, 1, 3],
        3: [1, 2, 4],
        4: [3]
    }

    max_colors_allowed = 3

    vertex_to_color_map = color_graph(graph_adjacency_list, 5)

    number_of_colors_used = len(set(vertex_to_color_map.values()))

    print(number_of_colors_used <= max_colors_allowed)