demo/coloring.cc
author deba
Wed, 21 Feb 2007 13:30:21 +0000
changeset 2376 0ed45a6c74b1
parent 2269 fb1c634fff29
child 2391 14a343be7a5a
permissions -rw-r--r--
Reorganization of the modules and groups
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup demos
    20 ///\file
    21 ///\brief Coloring of a graph.
    22 ///
    23 /// This example shows how can we color the nodes of a planar graph efficiently
    24 /// with six colors.
    25 ///
    26 /// \include coloring.cc
    27 
    28 #include <vector>
    29 
    30 #include <iostream>
    31 
    32 #include <lemon/smart_graph.h>
    33 #include <lemon/bucket_heap.h>
    34 #include <lemon/graph_reader.h>
    35 #include <lemon/graph_to_eps.h>
    36 
    37 #include <fstream>
    38 
    39 
    40 using namespace std;
    41 using namespace lemon;
    42 
    43 int main() {
    44 
    45   typedef SmartUGraph Graph;
    46   typedef Graph::Node Node;
    47   typedef Graph::NodeIt NodeIt;
    48   typedef Graph::UEdge UEdge;
    49   typedef Graph::IncEdgeIt IncEdgeIt;
    50 
    51   std::cout << "Six coloring of a planar graph" << std::endl;
    52   std::cout << "Input file: coloring.lgf" << std::endl;
    53   std::cout << "Output file: coloring.eps" << std::endl;
    54 
    55   Graph graph;
    56 
    57   UGraphReader<Graph> reader("coloring.lgf", graph);
    58   Graph::NodeMap<dim2::Point<double> > coords(graph);
    59   reader.readNodeMap("coords", coords);
    60   
    61   reader.run();
    62 
    63   Graph::NodeMap<int> color(graph, -2);
    64   
    65   Graph::NodeMap<int> heapMap(graph, -1);
    66   BucketHeap<Graph::NodeMap<int> > heap(heapMap);
    67   
    68   for (NodeIt it(graph); it != INVALID; ++it) {
    69     heap.push(it, countOutEdges(graph, it));
    70   }
    71 
    72   vector<Node> order;
    73 
    74   while (!heap.empty()) {
    75     Node node = heap.top();
    76     heap.pop();
    77     color[node] = -1;
    78     order.push_back(node);
    79     for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
    80       Node target = graph.runningNode(it); 
    81       if (color[target] == -2) {
    82 	heap.decrease(target, heap[target] - 1);
    83       }
    84     }
    85   }
    86 
    87   for (int i = order.size() - 1; i >= 0; --i) {
    88     set<int> forbidden;
    89     for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
    90       Node target = graph.runningNode(it); 
    91       if (color[target] != -1) {
    92 	forbidden.insert(color[target]);
    93       }
    94     }
    95     int current = 0;
    96     while (forbidden.find(current) != forbidden.end()) ++current;
    97     color[order[i]] = current;
    98   }
    99 
   100   Palette palette;
   101 
   102   graphToEps(graph, "coloring.eps").
   103     title("Six Colored Planar Graph").
   104     copyright("(C) 2006 LEMON Project").
   105     coords(coords).nodeColors(composeMap(palette, color)).
   106     nodeScale(5.0).scaleToA4().run();
   107 
   108   return 0;
   109 }