/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2008

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 ///\ingroup demos

 ///\file

 ///\brief Coloring of a graph.

 ///

 /// This example shows how can we color the nodes of a planar graph efficiently

 /// with six colors.

 ///

 /// \include coloring.cc

 #include <vector>

 #include <iostream>

 #include <lemon/smart_graph.h>

 #include <lemon/bucket_heap.h>

 #include <lemon/graph_reader.h>

 #include <lemon/graph_to_eps.h>

 #include <fstream>

 using namespace std;

 using namespace lemon;

 int main() {

   typedef SmartUGraph Graph;

   typedef Graph::Node Node;

   typedef Graph::NodeIt NodeIt;

   typedef Graph::UEdge UEdge;

   typedef Graph::IncEdgeIt IncEdgeIt;

   std::cout << "Six coloring of a planar graph" << std::endl;

   std::cout << "Input file: coloring.lgf" << std::endl;

   std::cout << "Output file: coloring.eps" << std::endl;

   Graph graph;

   UGraphReader<Graph> reader("coloring.lgf", graph);

   Graph::NodeMap<dim2::Point<double> > coords(graph);

   reader.readNodeMap("coords", coords);

   reader.run();

   Graph::NodeMap<int> color(graph, -2);

   Graph::NodeMap<int> heapMap(graph, -1);

   BucketHeap<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;

   }

   Palette palette;

   graphToEps(graph, "coloring.eps").

     title("Six Colored Planar Graph").

     copyright("(C) 2003-2007 LEMON Project").

     coords(coords).nodeColors(composeMap(palette, color)).

     nodeScale(5.0).scaleToA4().run();

   return 0;

 }