Moved SCL parser generator to platform repository.

[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / parser / generator / compression / GraphColoring.java

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/generator/compression/GraphColoring.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/generator/compression/GraphColoring.java
new file mode 100644 (file)
index 0000000..f0d261f
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/generator/compression/GraphColoring.java
@@ -0,0 +1,78 @@
+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;
+    }
+
+}