COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/coloring.cc @ 2070:1287ef6c180f

Last change on this file since 2070:1287ef6c180f was 2038:33db14058543, checked in by Balazs Dezso, 18 years ago

LinearHeap? is renamed to BucketHeap? which is more conform
and widely used name for this data structure

File size: 2.7 KB
Line 
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
40using namespace std;
41using namespace lemon;
42
43int 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<xy<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<Node, 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  ColorSet colorSet;
101
102  graphToEps(graph, "coloring.eps").
103    title("Six Colored Plan Graph").copyright("(C) 2006 LEMON Project").
104    coords(coords).nodeColors(composeMap(colorSet, color)).
105    nodeScale(5.0).scaleToA4().run();
106
107  return 0;
108}
Note: See TracBrowser for help on using the repository browser.