NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * demo/coloring.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 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) 2005 LEMON Project").
102 coords(coords).nodeColors(composeMap(colorSet, color)).
103 nodeScale(5.0).scaleToA4().run();