Small bug fixes.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
21 ///\brief Coloring of a graph.
23 /// This example shows how can we color the nodes of a planar graph efficiently
26 /// \include coloring.cc
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>
41 using namespace lemon;
45 typedef SmartUGraph Graph;
46 typedef Graph::Node Node;
47 typedef Graph::NodeIt NodeIt;
48 typedef Graph::UEdge UEdge;
49 typedef Graph::IncEdgeIt IncEdgeIt;
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;
57 UGraphReader<Graph> reader("coloring.lgf", graph);
58 Graph::NodeMap<dim2::Point<double> > coords(graph);
59 reader.readNodeMap("coords", coords);
63 Graph::NodeMap<int> color(graph, -2);
65 Graph::NodeMap<int> heapMap(graph, -1);
66 BucketHeap<Graph::NodeMap<int> > heap(heapMap);
68 for (NodeIt it(graph); it != INVALID; ++it) {
69 heap.push(it, countOutEdges(graph, it));
74 while (!heap.empty()) {
75 Node node = heap.top();
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);
87 for (int i = order.size() - 1; i >= 0; --i) {
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]);
96 while (forbidden.find(current) != forbidden.end()) ++current;
97 color[order[i]] = current;
102 graphToEps(graph, "coloring.eps").
103 title("Six Colored Planar Graph").
104 copyright("(C) 2003-2007 LEMON Project").
105 coords(coords).nodeColors(composeMap(palette, color)).
106 nodeScale(5.0).scaleToA4().run();