ladanyi@1636: /* -*- C++ -*-
ladanyi@1636:  * demo/coloring.cc - Part of LEMON, a generic C++ optimization library
ladanyi@1636:  *
alpar@1875:  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
ladanyi@1636:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
ladanyi@1636:  *
ladanyi@1636:  * Permission to use, modify and distribute this software is granted
ladanyi@1636:  * provided that this copyright notice appears in all copies. For
ladanyi@1636:  * precise terms see the accompanying LICENSE file.
ladanyi@1636:  *
ladanyi@1636:  * This software is provided "AS IS" with no warranty of any kind,
ladanyi@1636:  * express or implied, and with no claim as to its suitability for any
ladanyi@1636:  * purpose.
ladanyi@1636:  *
ladanyi@1636:  */
ladanyi@1636: 
deba@1727: ///\ingroup demos
deba@1727: ///\file
deba@1727: ///\brief Coloring of a graph.
deba@1727: ///
deba@1727: /// This example shows how can we color the nodes of a plan graph efficiently
deba@1727: /// with six colors.
deba@1727: ///
deba@1727: /// \include coloring.cc
deba@1727: 
deba@1422: #include <vector>
deba@1422: 
deba@1727: #include <iostream>
deba@1727: 
deba@1422: #include <lemon/smart_graph.h>
deba@1727: #include <lemon/linear_heap.h>
deba@1422: #include <lemon/graph_reader.h>
deba@1422: #include <lemon/graph_to_eps.h>
deba@1422: 
athos@1560: #include <fstream>
athos@1560: 
athos@1560: 
deba@1422: using namespace std;
deba@1422: using namespace lemon;
deba@1422: 
deba@1683: int main() {
athos@1560: 
deba@1422:   typedef UndirSmartGraph Graph;
deba@1422:   typedef Graph::Node Node;
deba@1422:   typedef Graph::NodeIt NodeIt;
deba@1422:   typedef Graph::UndirEdge UndirEdge;
deba@1422:   typedef Graph::IncEdgeIt IncEdgeIt;
deba@1422: 
deba@1683:   std::cout << "Six coloring of a plan graph" << std::endl;
deba@1683:   std::cout << "Input file: coloring.lgf" << std::endl;
deba@1683:   std::cout << "Output file: coloring.eps" << std::endl;
deba@1683: 
deba@1422:   Graph graph;
deba@1422: 
deba@1683:   UndirGraphReader<Graph> reader("coloring.lgf", graph);
deba@1422:   Graph::NodeMap<xy<double> > coords(graph);
deba@1422:   reader.readNodeMap("coords", coords);
deba@1422:   
deba@1422:   reader.run();
deba@1422: 
deba@1422:   Graph::NodeMap<int> color(graph, -2);
deba@1422:   
deba@1422:   Graph::NodeMap<int> heapMap(graph, -1);
deba@1727:   LinearHeap<Node, Graph::NodeMap<int> > heap(heapMap);
deba@1422:   
deba@1422:   for (NodeIt it(graph); it != INVALID; ++it) {
deba@1422:     heap.push(it, countOutEdges(graph, it));
deba@1422:   }
deba@1422: 
deba@1422:   vector<Node> order;
deba@1422: 
deba@1422:   while (!heap.empty()) {
deba@1422:     Node node = heap.top();
deba@1422:     heap.pop();
deba@1422:     color[node] = -1;
deba@1422:     order.push_back(node);
deba@1422:     for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
deba@1422:       Node target = graph.runningNode(it); 
deba@1422:       if (color[target] == -2) {
deba@1422: 	heap.decrease(target, heap[target] - 1);
deba@1422:       }
deba@1422:     }
deba@1422:   }
deba@1422: 
deba@1422:   for (int i = order.size() - 1; i >= 0; --i) {
deba@1422:     set<int> forbidden;
deba@1422:     for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
deba@1422:       Node target = graph.runningNode(it); 
deba@1422:       if (color[target] != -1) {
deba@1422: 	forbidden.insert(color[target]);
deba@1422:       }
deba@1422:     }
deba@1422:     int current = 0;
deba@1422:     while (forbidden.find(current) != forbidden.end()) ++current;
deba@1422:     color[order[i]] = current;
deba@1422:   }
deba@1422: 
deba@1422:   ColorSet colorSet;
deba@1422: 
deba@1683:   graphToEps(graph, "coloring.eps").
alpar@1875:     title("Six Colored Plan Graph").copyright("(C) 2006 LEMON Project").
deba@1422:     coords(coords).nodeColors(composeMap(colorSet, color)).
deba@1683:     nodeScale(5.0).scaleToA4().run();
deba@1422: 
deba@1422:   return 0;
deba@1422: }