/* -*- C++ -*-

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

 *

 * Copyright (C) 2006 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 plan graph efficiently

/// with six colors.

///

/// \include coloring.cc

#include <vector>

#include <iostream>

#include <lemon/smart_graph.h>

#include <lemon/linear_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 plan 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<xy<double> > coords(graph);

  reader.readNodeMap("coords", coords);

  reader.run();

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

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

  LinearHeap<Node, 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, "coloring.eps").

    title("Six Colored Plan Graph").copyright("(C) 2006 LEMON Project").

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

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

  return 0;

}