Several changes. \n If new map is added to mapstorage it emits signal with the name of the new map. This was important, because from now on not only tha mapwin should be updated. \n Furthermore algobox gets a pointer to mapstorage instead of only the mapnames from it. This is important because without it it would be complicated to pass all of the required maps to algobox.
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();