source: lemon-0.x/demo/coloring.cc @ 1435:8e85e6bbefdf

#include <vector>

#include <lemon/smart_graph.h>
#include <lemon/bin_heap.h>
#include <lemon/graph_reader.h>
#include <lemon/graph_to_eps.h>

using namespace std;
using namespace lemon;

int main() {
  typedef UndirSmartGraph Graph;
  typedef Graph::Node Node;
  typedef Graph::NodeIt NodeIt;
  typedef Graph::UndirEdge UndirEdge;
  typedef Graph::IncEdgeIt IncEdgeIt;

  Graph graph;

  UndirGraphReader<Graph> reader(std::cin, 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;
}