Not ready, but I commit it for simplicity.
3 #include <lemon/smart_graph.h>
4 #include <lemon/bin_heap.h>
5 #include <lemon/graph_reader.h>
6 #include <lemon/graph_to_eps.h>
12 typedef UndirSmartGraph Graph;
13 typedef Graph::Node Node;
14 typedef Graph::NodeIt NodeIt;
15 typedef Graph::UndirEdge UndirEdge;
16 typedef Graph::IncEdgeIt IncEdgeIt;
20 UndirGraphReader<Graph> reader(std::cin, graph);
21 Graph::NodeMap<xy<double> > coords(graph);
22 reader.readNodeMap("coords", coords);
26 Graph::NodeMap<int> color(graph, -2);
28 Graph::NodeMap<int> heapMap(graph, -1);
29 BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
31 for (NodeIt it(graph); it != INVALID; ++it) {
32 heap.push(it, countOutEdges(graph, it));
37 while (!heap.empty()) {
38 Node node = heap.top();
41 order.push_back(node);
42 for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
43 Node target = graph.runningNode(it);
44 if (color[target] == -2) {
45 heap.decrease(target, heap[target] - 1);
50 for (int i = order.size() - 1; i >= 0; --i) {
52 for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
53 Node target = graph.runningNode(it);
54 if (color[target] != -1) {
55 forbidden.insert(color[target]);
59 while (forbidden.find(current) != forbidden.end()) ++current;
60 color[order[i]] = current;
65 graphToEps(graph, "six_coloring.eps").
66 title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
67 coords(coords).nodeColors(composeMap(colorSet, color)).