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