deba@1422: #include <vector>
deba@1422: 
deba@1422: #include <lemon/smart_graph.h>
deba@1422: #include <lemon/bin_heap.h>
deba@1422: #include <lemon/graph_reader.h>
deba@1422: #include <lemon/graph_to_eps.h>
deba@1422: 
deba@1422: using namespace std;
deba@1422: using namespace lemon;
deba@1422: 
deba@1422: int main() {
deba@1422:   typedef UndirSmartGraph Graph;
deba@1422:   typedef Graph::Node Node;
deba@1422:   typedef Graph::NodeIt NodeIt;
deba@1422:   typedef Graph::UndirEdge UndirEdge;
deba@1422:   typedef Graph::IncEdgeIt IncEdgeIt;
deba@1422: 
deba@1422:   Graph graph;
deba@1422: 
deba@1422:   UndirGraphReader<Graph> reader(std::cin, graph);
deba@1422:   Graph::NodeMap<xy<double> > coords(graph);
deba@1422:   reader.readNodeMap("coords", coords);
deba@1422:   
deba@1422:   reader.run();
deba@1422: 
deba@1422:   Graph::NodeMap<int> color(graph, -2);
deba@1422:   
deba@1422:   Graph::NodeMap<int> heapMap(graph, -1);
deba@1422:   BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
deba@1422:   
deba@1422:   for (NodeIt it(graph); it != INVALID; ++it) {
deba@1422:     heap.push(it, countOutEdges(graph, it));
deba@1422:   }
deba@1422: 
deba@1422:   vector<Node> order;
deba@1422: 
deba@1422:   while (!heap.empty()) {
deba@1422:     Node node = heap.top();
deba@1422:     heap.pop();
deba@1422:     color[node] = -1;
deba@1422:     order.push_back(node);
deba@1422:     for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
deba@1422:       Node target = graph.runningNode(it); 
deba@1422:       if (color[target] == -2) {
deba@1422: 	heap.decrease(target, heap[target] - 1);
deba@1422:       }
deba@1422:     }
deba@1422:   }
deba@1422: 
deba@1422:   for (int i = order.size() - 1; i >= 0; --i) {
deba@1422:     set<int> forbidden;
deba@1422:     for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
deba@1422:       Node target = graph.runningNode(it); 
deba@1422:       if (color[target] != -1) {
deba@1422: 	forbidden.insert(color[target]);
deba@1422:       }
deba@1422:     }
deba@1422:     int current = 0;
deba@1422:     while (forbidden.find(current) != forbidden.end()) ++current;
deba@1422:     color[order[i]] = current;
deba@1422:   }
deba@1422: 
deba@1422:   ColorSet colorSet;
deba@1422: 
deba@1422:   graphToEps(graph, "six_coloring.eps").
deba@1422:     title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
deba@1422:     coords(coords).nodeColors(composeMap(colorSet, color)).
deba@1422:     scaleToA4().run();
deba@1422: 
deba@1422:   return 0;
deba@1422: }