Algorithm to (greedily) approximate the chromatic number of a graph.

chromatic_number.py

import itertools
import re


def UniqueList(data):
    return list(set(data))


class Graph:
    def __init__(self, vertices, edges):
        self.vertices = UniqueList(vertices)
        self.edges = UniqueList(edges)

    def areAdjacent(self, u, v):
        for edge in self.edges:
            if edge == (u, v):
                return True
        return False

    def vertexDegree(self, vertex):
        degree = 0
        for edge in self.edges:
            if edge[0] == vertex or edge[1] == vertex:
                degree = degree + 1
        return degree

    def adjacentColoredWith(self, vertex, colors, new_color):
        for color in colors:
            if color[1] != new_color:
                continue
            if (vertex, color[0]) in self.edges or (color[0], vertex) in self.edges:
                return True
        return False

    def chromatic_number(self):
        sorted_vertices = sorted(self.vertices, key=lambda x: self.vertexDegree(x), reverse=True)
        print(sorted_vertices)

        colors = []
        last_color = 1

        def alreadyColored(vertex, colors):
            for color in colors:
                if color[0] == vertex:
                    return True
            return False

        for vertex in sorted_vertices:
            if not alreadyColored(vertex, colors):
                colors.append((vertex, last_color))
                # Color all the non-adjacent vertices with this color
                for other_vertex in self.vertices:
                    if (vertex, other_vertex) in self.edges or (other_vertex, vertex) in self.edges:
                        continue
                    if alreadyColored(other_vertex, colors):
                        continue
                    if self.adjacentColoredWith(other_vertex, colors, last_color):
                        continue
                    colors.append((other_vertex, last_color))
                last_color = last_color + 1

        print(colors)
        return last_color - 1


def ParseVertices(input):
    verts = input.split(',')
    verts = list(map(str.strip, verts))
    if len(verts) > 0:
        return verts
    return None


def ParseEdges(input):
    def CreateEdge(edge):
        elements = edge.split(';')
        elements = list(map(str.strip, elements))
        if len(elements) != 2:
            raise Exception('Arista inválida')
        if len(elements[0]) < 1 or len(elements[1]) < 1:
            raise Exception('Arista inválida')
        edge = (elements[0][1:], elements[1][:-1])
        return tuple(map(str.strip, edge))

    # Allow empty edge sets
    if not input.strip():
        return []

    edges = input.split(',')
    edges = list(map(str.strip, edges))
    try:
        edges = list(map(CreateEdge, edges))
    except:
        return None

    return edges


while True:
    print('Digite los vértices del grafo A, separados por coma (,)')
    Va = ParseVertices(input())
    if Va is not None:
        break
    print('Vértices inválidos')

while True:
    print('Digite las aristas del grafo A, separadas por coma (,), en la forma (v; u), ejemplo: "(v1; v2), (v2; v3), (v3; v4)"')
    Ea = ParseEdges(input())
    if Ea is not None:
        break
    print('Aristas inválidas')

A = Graph(Va, Ea)

print('==' * 10)
print('El grafo acepta una coloración con {} colores'.format(A.chromatic_number()))