1 package org.simantics.scl.compiler.parser.generator.compression;
4 public class GraphColoring {
6 public static interface ColGraph {
8 boolean areConnected(int a, int b);
12 * Finds a coloring of the graph so that all connected vertices
13 * have a different color. Returns the number of colors used.
15 public static int color(int[] color, ColGraph graph) {
16 int size = graph.size();
18 // unassigned/unassignedCount is a list of unassigned vertex ids
19 int[] unassigned = new int[size];
20 for(int i=0;i<size;++i)
22 int unassignedCount = size;
24 // blockedCount[vertexId] is the number of blocked colors for vertexId
25 int[] blockedCount = new int[size];
27 // blocked[color][vertexId] is true, if color is not a possible color for vertexId
28 boolean[][] blocked = new boolean[size][size];
30 // Number of colors currently in use
33 while(unassignedCount > 0) {
34 // Choose a vertex is bestId from unassigned list so that
35 // bestBlockedCount=blockedCount[bestId] is maximized
37 int bestUnassignedTableId = 0;
38 int bestBlockedCount = -1;
39 for(int i=0;i<unassignedCount;++i) {
40 int id = unassigned[i];
41 int tempCount = blockedCount[id];
42 if(tempCount > bestBlockedCount) {
43 bestUnassignedTableId = i;
45 bestBlockedCount = tempCount;
49 // Remove from unassigned table
50 unassigned[bestUnassignedTableId] = unassigned[--unassignedCount];
54 if(bestBlockedCount == colorCount) // All colors are blocked
55 chosenColor = colorCount++;
56 else { // There is unblocked color
57 for(int i=0;i<colorCount;++i)
58 if(!blocked[i][bestId]) {
63 color[bestId] = chosenColor;
65 // Update blocked table
66 boolean[] blockedRow = blocked[chosenColor];
67 for(int i=0;i<unassignedCount;++i) {
68 int id = unassigned[i];
69 if(!blockedRow[id] && graph.areConnected(bestId, id)) {
70 blockedRow[id] = true;