Do not append -Wall -W to CXXFLAGS when it is set on the commandline.
2 * demo/coloring.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
19 ///\brief Coloring of a graph.
21 /// This example shows how can we color the nodes of a plan graph efficiently
24 /// \include coloring.cc
30 #include <lemon/smart_graph.h>
31 #include <lemon/linear_heap.h>
32 #include <lemon/graph_reader.h>
33 #include <lemon/graph_to_eps.h>
39 using namespace lemon;
43 typedef UndirSmartGraph Graph;
44 typedef Graph::Node Node;
45 typedef Graph::NodeIt NodeIt;
46 typedef Graph::UndirEdge UndirEdge;
47 typedef Graph::IncEdgeIt IncEdgeIt;
49 std::cout << "Six coloring of a plan graph" << std::endl;
50 std::cout << "Input file: coloring.lgf" << std::endl;
51 std::cout << "Output file: coloring.eps" << std::endl;
55 UndirGraphReader<Graph> reader("coloring.lgf", graph);
56 Graph::NodeMap<xy<double> > coords(graph);
57 reader.readNodeMap("coords", coords);
61 Graph::NodeMap<int> color(graph, -2);
63 Graph::NodeMap<int> heapMap(graph, -1);
64 LinearHeap<Node, Graph::NodeMap<int> > heap(heapMap);
66 for (NodeIt it(graph); it != INVALID; ++it) {
67 heap.push(it, countOutEdges(graph, it));
72 while (!heap.empty()) {
73 Node node = heap.top();
76 order.push_back(node);
77 for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
78 Node target = graph.runningNode(it);
79 if (color[target] == -2) {
80 heap.decrease(target, heap[target] - 1);
85 for (int i = order.size() - 1; i >= 0; --i) {
87 for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
88 Node target = graph.runningNode(it);
89 if (color[target] != -1) {
90 forbidden.insert(color[target]);
94 while (forbidden.find(current) != forbidden.end()) ++current;
95 color[order[i]] = current;
100 graphToEps(graph, "coloring.eps").
101 title("Six Colored Plan Graph").copyright("(C) 2006 LEMON Project").
102 coords(coords).nodeColors(composeMap(colorSet, color)).
103 nodeScale(5.0).scaleToA4().run();