source: lemon-0.x/demo/coloring.cc @ 1637:9d64d5672b88

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