Update ChangeLog.
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 #include <lemon/smart_graph.h>
20 #include <lemon/bin_heap.h>
21 #include <lemon/graph_reader.h>
22 #include <lemon/graph_to_eps.h>
29 using namespace lemon;
31 int main(int argc, char *argv[])
35 std::cerr << "USAGE: coloring input_file.lgf" << std::endl;
36 std::cerr << "The file 'input_file.lgf' has to contain a graph in LEMON format together with a nodemap called 'coords' to draw the graph (e.g. sample.lgf is not such a file)." << std::endl;
41 //input stream to read the graph from
42 std::ifstream is(argv[1]);
44 typedef UndirSmartGraph Graph;
45 typedef Graph::Node Node;
46 typedef Graph::NodeIt NodeIt;
47 typedef Graph::UndirEdge UndirEdge;
48 typedef Graph::IncEdgeIt IncEdgeIt;
52 UndirGraphReader<Graph> reader(is, graph);
53 Graph::NodeMap<xy<double> > coords(graph);
54 reader.readNodeMap("coords", coords);
58 Graph::NodeMap<int> color(graph, -2);
60 Graph::NodeMap<int> heapMap(graph, -1);
61 BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
63 for (NodeIt it(graph); it != INVALID; ++it) {
64 heap.push(it, countOutEdges(graph, it));
69 while (!heap.empty()) {
70 Node node = heap.top();
73 order.push_back(node);
74 for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
75 Node target = graph.runningNode(it);
76 if (color[target] == -2) {
77 heap.decrease(target, heap[target] - 1);
82 for (int i = order.size() - 1; i >= 0; --i) {
84 for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
85 Node target = graph.runningNode(it);
86 if (color[target] != -1) {
87 forbidden.insert(color[target]);
91 while (forbidden.find(current) != forbidden.end()) ++current;
92 color[order[i]] = current;
97 graphToEps(graph, "six_coloring.eps").
98 title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
99 coords(coords).nodeColors(composeMap(colorSet, color)).