Colorear un grafo

ℹ️

Este algoritmo resuelve el problema de los colores en los mapas

De que color tengo que pintar cada país, para que no coincida con ningún país con los que hace frontera

Este algoritmo en concreto devuelve, dado un número de colores, como deberíamos pintar cada nodo, o si no se puede con los colores disponibles

"""
    Graph coloring problem using backtracking
    
    Given a graph, the goal is to assign colors to each node in such a way that no two adjacent nodes have the same color
    
"""

# Verifies if a color is feasible for a node by checking if it is different from the colors of its adjacent nodes
def isFeasible(graph, currentSol, currentNode, color):
    adjacency = graph["adjacency"][currentNode]
    for adj in adjacency:
        if adj < currentNode and currentSol[adj] == color:
            return False
        
    return True

# Determines if the current solution is complete by checking if the last node was colored (last node was (n-1) so currentNode will be out of bounds once it has been colored all nodes)
def isSol(currentNode, graph):
    return currentNode == graph["n"]

# Colors the graph using backtracking
def colorGraph(graph, colors, currentSol, currentNode):
    """
        - graph: dictionary containing the graph information {n: number of nodes, adjacency: adjacency list}
        - colors: number of available colors (from 0 to (colors-1)) being -1 the absence of color
        - currentSol: list containing the current solution
        - currentNode: current node being colored (no further nodes are colored yet)
    """
    # Check if the current solution is complete (all nodes were colored)
    if isSol(currentNode, graph):
        return True
    else:
        # Try to color the node with each color
        for color in range(colors):
            # Check if the color is feasible
            if isFeasible(graph, currentSol, currentNode, color):
                currentSol[currentNode] = color
                valid = colorGraph(graph, colors, currentSol, currentNode + 1)
                
                # If the color is not valid, backtrack (remove the color from the current node and try with the next color)
                if not valid:
                    currentSol[currentNode] = -1
                # The backtracking base case was reached, so the solution is complete
                else:
                    return True

# Main function
if __name__ == "__main__":
    # Parameters
    colors = 3 # Number of available colors
    first = 0 # First node to color
    
    # Create a graph
    graph = {
        "n": 4,
        "adjacency": [[1, 2, 3], [0], [0, 3], [0, 2]]
    }
    # Initialize the current solution
    currentSol = [-1] * graph["n"]
    
    # Color the graph, the solution is stored in currentSol, if the solution is not possible, currentSol will be [-1, -1, ..., -1]
    colorGraph(graph, colors, currentSol, first)
    
    print(currentSol)