package org.simantics.scl.compiler.parser.generator.compression;


public class GraphColoring {

    public static interface ColGraph {
        int size();
        boolean areConnected(int a, int b);
    }

    /**
     * Finds a coloring of the graph so that all connected vertices
     * have a different color. Returns the number of colors used.
     */
    public static int color(int[] color, ColGraph graph) {
        int size = graph.size();

        // unassigned/unassignedCount is a list of unassigned vertex ids
        int[] unassigned = new int[size];
        for(int i=0;i<size;++i)
            unassigned[i] = i;
        int unassignedCount = size;

        // blockedCount[vertexId] is the number of blocked colors for vertexId
        int[] blockedCount = new int[size];
        
        // blocked[color][vertexId] is true, if color is not a possible color for vertexId
        boolean[][] blocked = new boolean[size][size];
        
        // Number of colors currently in use
        int colorCount = 0;

        while(unassignedCount > 0) {
            // Choose a vertex is bestId from unassigned list so that
            // bestBlockedCount=blockedCount[bestId] is maximized
            int bestId = 0;
            int bestUnassignedTableId = 0;
            int bestBlockedCount = -1;
            for(int i=0;i<unassignedCount;++i) {
                int id = unassigned[i];
                int tempCount = blockedCount[id];
                if(tempCount > bestBlockedCount) {
                    bestUnassignedTableId = i;
                    bestId = id;
                    bestBlockedCount = tempCount;
                }
            }

            // Remove from unassigned table
            unassigned[bestUnassignedTableId] = unassigned[--unassignedCount];

            // Choose color
            int chosenColor = 0;
            if(bestBlockedCount == colorCount) // All colors are blocked 
                chosenColor = colorCount++;
            else { // There is unblocked color
                for(int i=0;i<colorCount;++i)
                    if(!blocked[i][bestId]) {
                        chosenColor = i;
                        break;
                    }
            }
            color[bestId] = chosenColor;

            // Update blocked table
            boolean[] blockedRow = blocked[chosenColor];
            for(int i=0;i<unassignedCount;++i) {
                int id = unassigned[i];
                if(!blockedRow[id] && graph.areConnected(bestId, id)) {
                    blockedRow[id] = true;
                    ++blockedCount[id];
                }
            }
        }
        return colorCount;
    }

}