/* -*- 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;

}