ladanyi@1636: /* -*- C++ -*-
ladanyi@1636:  * demo/coloring.cc - Part of LEMON, a generic C++ optimization library
ladanyi@1636:  *
ladanyi@1636:  * Copyright (C) 2005 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@1422: #include <vector>
deba@1422: 
deba@1422: #include <lemon/smart_graph.h>
deba@1422: #include <lemon/bin_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: #include <iostream>
athos@1560: 
athos@1560: 
deba@1422: using namespace std;
deba@1422: using namespace lemon;
deba@1422: 
athos@1560: int main(int argc, char *argv[]) 
athos@1560: {
athos@1560:   if(argc<2)
athos@1560:   {
athos@1577:       std::cerr << "USAGE: coloring input_file.lgf" << std::endl;
athos@1560:       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;
athos@1560:       return 0;
athos@1560:   }
athos@1560: 
athos@1560: 
athos@1560:   //input stream to read the graph from
athos@1560:   std::ifstream is(argv[1]);
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@1422:   Graph graph;
deba@1422: 
athos@1560:   UndirGraphReader<Graph> reader(is, 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@1422:   BinHeap<Node, int, 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@1422:   graphToEps(graph, "six_coloring.eps").
deba@1422:     title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
deba@1422:     coords(coords).nodeColors(composeMap(colorSet, color)).
deba@1422:     scaleToA4().run();
deba@1422: 
deba@1422:   return 0;
deba@1422: }