source: lemon-0.x/demo/coloring.cc

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