From 42341d8fd3cd701e10bdf69c12267dea61374cb8 Mon Sep 17 00:00:00 2001
From: ian <ian>
Date: Wed, 9 Apr 2008 22:58:29 +0000
Subject: [PATCH] nice graph colourings

---
 layout/redactgraph.c | 88 +++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 82 insertions(+), 6 deletions(-)

diff --git a/layout/redactgraph.c b/layout/redactgraph.c
index 09bc197..3b55b54 100644
--- a/layout/redactgraph.c
+++ b/layout/redactgraph.c
@@ -727,9 +727,22 @@ static void printforforsafety(void) {
 
 static void printforlayoutsegjoins(void) {
   Node *node;
-  EdgeEnd *edgeend;
-  Segment **segmentp, *segment;
-  int side;
+  EdgeEnd *edgeend, *edgeend2;
+  Segment **segmentp, *segment, *segment2;
+  int side, side2, order, max_order, colour, any_left;
+  
+  /* we format segment->u as follows: */
+#define LSJ_U_VERTEXORDER_MASK 0x000000ff
+#define LSJ_U_COLOUR_SHIFT                8
+#define LSJ_U_COLOUR_BITS                 16
+#define LSJ_U_COLOUR_UNIT                 (1<<LSJ_U_COLOUR_SHIFT)
+#define LSJ_U_COLOUR_MASK      0x00ffff00
+#define LSJ_U_SEGEND_DONE      0x01000000
+#define LSJ_U_COLOUR_CLASH     0x02000000
+
+  max_order= 0;
+  FOR_ALL_SEGMENTS(segmentp,segment)
+    segment->u= 0;
   
   FOR_ALL_NODES(node) {
     output("layer ");
@@ -746,14 +759,77 @@ static void printforlayoutsegjoins(void) {
     FOR_NODE_EDGEENDS(side,edgeend, node)
       output("_%s",edgeend->edge->subseg->segment->segname);
     output(" %f %f %f\n", node->x,node->y,node->a);
-    FOR_ALL_SEGMENTS(segmentp,segment) segment->u= 0;
     FOR_NODE_EDGEENDS(side,edgeend, node) {
       segment= edgeend->edge->subseg->segment;
-      if (segment->u++) continue;
+      if (segment->u & LSJ_U_SEGEND_DONE) continue;
+      segment->u |= LSJ_U_SEGEND_DONE;
+      assert(~segment->u & LSJ_U_VERTEXORDER_MASK); /* detect overflow */
+      segment->u++;
+      order= segment->u & LSJ_U_VERTEXORDER_MASK;
+      if (order > max_order) max_order= order;
       output("segend %s\n",segment->segname);
-      output("segcmap %s  0.5 setgray\n",segment->segname);
     }
     output("\n");
+    FOR_ALL_SEGMENTS(segmentp,segment)
+      segment->u &= ~LSJ_U_SEGEND_DONE;
+  }
+
+  /* Welsh and Powell's graph colouring algorithm
+   * (Wikipedia Graph_coloring) */
+  output("# max-order %d\n",max_order);
+
+  for (colour=LSJ_U_COLOUR_UNIT, any_left=1;
+       any_left;
+       colour+=LSJ_U_COLOUR_UNIT) {
+    output("# colour %x\n", colour);
+    assert(!(colour & ~LSJ_U_COLOUR_MASK));
+   something_done:
+    any_left= 0;
+
+    FOR_ALL_SEGMENTS(segmentp,segment)
+      segment->u &= ~LSJ_U_COLOUR_CLASH;
+
+    FOR_ALL_NODES(node)
+      FOR_NODE_EDGEENDS(side,edgeend, node) {
+        segment= edgeend->edge->subseg->segment;
+	if (colour == (segment->u & LSJ_U_COLOUR_MASK)) {
+	  output("#  already %s\n", segment->segname);
+	  FOR_NODE_EDGEENDS(side2,edgeend2, node) {
+	    segment2= edgeend2->edge->subseg->segment;
+	    output("#   therefore-not %s\n", segment2->segname);
+	    segment2->u |= LSJ_U_COLOUR_CLASH;
+	  }
+	}
+      }
+
+    for (order=max_order; order>0; order--) { /* idiot-sort */
+      output("#  order %d\n", order);
+      FOR_ALL_SEGMENTS(segmentp,segment)
+	if ((segment->u & LSJ_U_VERTEXORDER_MASK) == order) {
+	  if (segment->u & LSJ_U_COLOUR_MASK) continue;
+	  any_left= 1;
+	  if (segment->u & LSJ_U_COLOUR_CLASH) {
+	    output("#   still-clashes %s\n", segment->segname);
+	    continue;
+	  }
+	  segment->u |= colour;
+	  output("#   coloured %s\n", segment->segname);
+	  goto something_done;
+	} else {
+	  output("# (skip %s %x)\n", segment->segname,segment->u);
+	}
+    }
+  }
+
+  FOR_ALL_SEGMENTS(segmentp,segment) {
+    int tcolour= segment->u & LSJ_U_COLOUR_MASK;
+    const double val1=0.75, val2=0.50;
+    double value;
+    if (!tcolour) continue;
+    value= val1 +
+	     (tcolour - LSJ_U_COLOUR_UNIT*2) * (val1-val2) /
+	     (colour - LSJ_U_COLOUR_UNIT*2);
+    output("segcmap %s  %f setgray\n", segment->segname,value);
   }
 }
 
-- 
2.30.2