/* -*- C++ -*-

  * demo/coloring.cc - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2005 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.

  *

  */

 #include <vector>

 #include <lemon/smart_graph.h>

 #include <lemon/bin_heap.h>

 #include <lemon/graph_reader.h>

 #include <lemon/graph_to_eps.h>

 #include <fstream>

 #include <iostream>

 using namespace std;

 using namespace lemon;

 int main(int argc, char *argv[]) 

 {

   if(argc<2)

   {

       std::cerr << "USAGE: coloring input_file.lgf" << std::endl;

       std::cerr << "The file 'input_file.lgf' has to contain a graph in LEMON format together with a nodemap called 'coords' to draw the graph (e.g. sample.lgf is not such a file)." << std::endl;

       return 0;

   }

   //input stream to read the graph from

   std::ifstream is(argv[1]);

   typedef UndirSmartGraph Graph;

   typedef Graph::Node Node;

   typedef Graph::NodeIt NodeIt;

   typedef Graph::UndirEdge UndirEdge;

   typedef Graph::IncEdgeIt IncEdgeIt;

   Graph graph;

   UndirGraphReader<Graph> reader(is, 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;

 }