ladanyi@1636: /* -*- C++ -*-
ladanyi@1636:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
ladanyi@1636:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
ladanyi@1636:  *
ladanyi@1636:  * Permission to use, modify and distribute this software is granted
ladanyi@1636:  * provided that this copyright notice appears in all copies. For
ladanyi@1636:  * precise terms see the accompanying LICENSE file.
ladanyi@1636:  *
ladanyi@1636:  * This software is provided "AS IS" with no warranty of any kind,
ladanyi@1636:  * express or implied, and with no claim as to its suitability for any
ladanyi@1636:  * purpose.
ladanyi@1636:  *
ladanyi@1636:  */
ladanyi@1636: 
deba@1727: ///\ingroup demos
deba@1727: ///\file
deba@1727: ///\brief Coloring of a graph.
deba@1727: ///
alpar@1959: /// This example shows how can we color the nodes of a planar graph efficiently
deba@1727: /// with six colors.
deba@1727: ///
deba@1727: /// \include coloring.cc
deba@1727: 
deba@1422: #include <vector>
deba@1422: 
deba@1727: #include <iostream>
deba@1727: 
deba@2116: #include <lemon/smart_graph.h>
deba@2038: #include <lemon/bucket_heap.h>
deba@1422: #include <lemon/graph_reader.h>
deba@1422: #include <lemon/graph_to_eps.h>
deba@1422: 
athos@1560: #include <fstream>
athos@1560: 
athos@1560: 
deba@1422: using namespace std;
deba@1422: using namespace lemon;
deba@1422: 
deba@1683: int main() {
athos@1560: 
klao@1909:   typedef SmartUGraph Graph;
deba@1422:   typedef Graph::Node Node;
deba@1422:   typedef Graph::NodeIt NodeIt;
klao@1909:   typedef Graph::UEdge UEdge;
deba@1422:   typedef Graph::IncEdgeIt IncEdgeIt;
deba@1422: 
alpar@1959:   std::cout << "Six coloring of a planar graph" << std::endl;
deba@1683:   std::cout << "Input file: coloring.lgf" << std::endl;
deba@1683:   std::cout << "Output file: coloring.eps" << std::endl;
deba@1683: 
deba@1422:   Graph graph;
deba@1422: 
klao@1909:   UGraphReader<Graph> reader("coloring.lgf", graph);
alpar@2207:   Graph::NodeMap<dim2::Point<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@2269:   BucketHeap<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: 
alpar@2172:   Palette palette;
deba@1422: 
deba@1683:   graphToEps(graph, "coloring.eps").
deba@2359:     title("Six Colored Planar Graph").
alpar@2391:     copyright("(C) 2003-2007 LEMON Project").
alpar@2172:     coords(coords).nodeColors(composeMap(palette, color)).
deba@1683:     nodeScale(5.0).scaleToA4().run();
deba@1422: 
deba@1422:   return 0;
deba@1422: }