bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/generator/compression/GraphColoring.java

   1 package org.simantics.scl.compiler.parser.generator.compression;
   2
   3
   4 public class GraphColoring {
   5
   6     public static interface ColGraph {
   7         int size();
   8         boolean areConnected(int a, int b);
   9     }
  10
  11     /**
  12      * Finds a coloring of the graph so that all connected vertices
  13      * have a different color. Returns the number of colors used.
  14      */
  15     public static int color(int[] color, ColGraph graph) {
  16         int size = graph.size();
  17
  18         // unassigned/unassignedCount is a list of unassigned vertex ids
  19         int[] unassigned = new int[size];
  20         for(int i=0;i<size;++i)
  21             unassigned[i] = i;
  22         int unassignedCount = size;
  23
  24         // blockedCount[vertexId] is the number of blocked colors for vertexId
  25         int[] blockedCount = new int[size];
  26
  27         // blocked[color][vertexId] is true, if color is not a possible color for vertexId
  28         boolean[][] blocked = new boolean[size][size];
  29
  30         // Number of colors currently in use
  31         int colorCount = 0;
  32
  33         while(unassignedCount > 0) {
  34             // Choose a vertex is bestId from unassigned list so that
  35             // bestBlockedCount=blockedCount[bestId] is maximized
  36             int bestId = 0;
  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;
  44                     bestId = id;
  45                     bestBlockedCount = tempCount;
  46                 }
  47             }
  48
  49             // Remove from unassigned table
  50             unassigned[bestUnassignedTableId] = unassigned[--unassignedCount];
  51
  52             // Choose color
  53             int chosenColor = 0;
  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]) {
  59                         chosenColor = i;
  60                         break;
  61                     }
  62             }
  63             color[bestId] = chosenColor;
  64
  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;
  71                     ++blockedCount[id];
  72                 }
  73             }
  74         }
  75         return colorCount;
  76     }
  77
  78 }