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