# HG changeset patch
# User deba
# Date 1116092445 0
# Node ID 469b3f628dd15c5952f4a5ca43cde06eb1740952
# Parent  7a21e1414c38fcfa8d82f31b2ecc0846900c5040
Six-coloring in plan graphs.

diff -r 7a21e1414c38 -r 469b3f628dd1 src/demo/Makefile.am
--- a/src/demo/Makefile.am	Sat May 14 17:39:37 2005 +0000
+++ b/src/demo/Makefile.am	Sat May 14 17:40:45 2005 +0000
@@ -8,7 +8,8 @@
 	dim_to_lgf \
 	graph_to_eps_demo \
 	min_route \
-	sub_graph_adaptor_demo
+	sub_graph_adaptor_demo \
+	coloring
 
 if HAVE_GLPK
 noinst_PROGRAMS += lp_demo lp_maxflow_demo
@@ -23,6 +24,8 @@
 
 dim_to_lgf_SOURCES = dim_to_lgf.cc
 
+coloring_SOURCES = coloring.cc
+
 graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
 
 min_route_SOURCES = min_route.cc
diff -r 7a21e1414c38 -r 469b3f628dd1 src/demo/coloring.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/demo/coloring.cc	Sat May 14 17:40:45 2005 +0000
@@ -0,0 +1,71 @@
+#include <vector>
+
+#include <lemon/smart_graph.h>
+#include <lemon/bin_heap.h>
+#include <lemon/graph_reader.h>
+#include <lemon/graph_to_eps.h>
+
+using namespace std;
+using namespace lemon;
+
+int main() {
+  typedef UndirSmartGraph Graph;
+  typedef Graph::Node Node;
+  typedef Graph::NodeIt NodeIt;
+  typedef Graph::UndirEdge UndirEdge;
+  typedef Graph::IncEdgeIt IncEdgeIt;
+
+  Graph graph;
+
+  UndirGraphReader<Graph> reader(std::cin, graph);
+  Graph::NodeMap<xy<double> > coords(graph);
+  reader.readNodeMap("coords", coords);
+  
+  reader.run();
+
+  Graph::NodeMap<int> color(graph, -2);
+  
+  Graph::NodeMap<int> heapMap(graph, -1);
+  BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
+  
+  for (NodeIt it(graph); it != INVALID; ++it) {
+    heap.push(it, countOutEdges(graph, it));
+  }
+
+  vector<Node> order;
+
+  while (!heap.empty()) {
+    Node node = heap.top();
+    heap.pop();
+    color[node] = -1;
+    order.push_back(node);
+    for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
+      Node target = graph.runningNode(it); 
+      if (color[target] == -2) {
+	heap.decrease(target, heap[target] - 1);
+      }
+    }
+  }
+
+  for (int i = order.size() - 1; i >= 0; --i) {
+    set<int> forbidden;
+    for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
+      Node target = graph.runningNode(it); 
+      if (color[target] != -1) {
+	forbidden.insert(color[target]);
+      }
+    }
+    int current = 0;
+    while (forbidden.find(current) != forbidden.end()) ++current;
+    color[order[i]] = current;
+  }
+
+  ColorSet colorSet;
+
+  graphToEps(graph, "six_coloring.eps").
+    title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
+    coords(coords).nodeColors(composeMap(colorSet, color)).
+    scaleToA4().run();
+
+  return 0;
+}