Greedy algo for the GCP

graph_colouring_greedy.py

import numpy as np

def greedy_graph_colouring(edge_array: np.array):
    def color_nodes(graph):
        color_map = {}
        # Consider nodes in descending degree
        for node in sorted(graph, key=lambda x: len(graph[x]), reverse=True):
            neighbor_colors = set(color_map.get(neigh) for neigh in graph[node])
            color_map[node] = next(
                color for color in range(len(graph)) if color not in neighbor_colors
            )
        return color_map

    node_neighbour_dict = {}

    for edge_index in range(edge_array.shape[0]):
        v0, v1 = int(edge_array[edge_index, 0]), int(edge_array[edge_index, 1])
        if v0 not in node_neighbour_dict:
            node_neighbour_dict[v0] = []
        node_neighbour_dict[v0].append(v1)
        if v1 not in node_neighbour_dict:
            node_neighbour_dict[v1] = []
        node_neighbour_dict[v1].append(v0)

    solution_dict = color_nodes(node_neighbour_dict)

    solution_array = np.zeros(int(edge_array.max() + 1))
    obj_val = 0
    for i in range(int(edge_array.max() + 1)):
        colour = solution_dict[i]
        solution_array[i] = colour
        obj_val = max(obj_val, colour)

    out_dict = {
        'solution_array': solution_array.astype(int),
        'num_colours': obj_val + 1
    }

    return out_dict['num_colours']