/* -*- C++ -*- * demo/coloring.cc - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ ///\ingroup demos ///\file ///\brief Coloring of a graph. /// /// This example shows how can we color the nodes of a plan graph efficiently /// with six colors. /// /// \include coloring.cc #include #include #include #include #include #include #include using namespace std; using namespace lemon; int main() { typedef UndirSmartGraph Graph; typedef Graph::Node Node; typedef Graph::NodeIt NodeIt; typedef Graph::UndirEdge UndirEdge; typedef Graph::IncEdgeIt IncEdgeIt; std::cout << "Six coloring of a plan graph" << std::endl; std::cout << "Input file: coloring.lgf" << std::endl; std::cout << "Output file: coloring.eps" << std::endl; Graph graph; UndirGraphReader reader("coloring.lgf", graph); Graph::NodeMap > coords(graph); reader.readNodeMap("coords", coords); reader.run(); Graph::NodeMap color(graph, -2); Graph::NodeMap heapMap(graph, -1); LinearHeap > heap(heapMap); for (NodeIt it(graph); it != INVALID; ++it) { heap.push(it, countOutEdges(graph, it)); } vector order; while (!heap.empty()) { Node node = heap.top(); heap.pop(); color[node] = -1; order.push_back(node); for (IncEdgeIt it(graph, node); it != INVALID; ++it) { Node target = graph.runningNode(it); if (color[target] == -2) { heap.decrease(target, heap[target] - 1); } } } for (int i = order.size() - 1; i >= 0; --i) { set forbidden; for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) { Node target = graph.runningNode(it); if (color[target] != -1) { forbidden.insert(color[target]); } } int current = 0; while (forbidden.find(current) != forbidden.end()) ++current; color[order[i]] = current; } ColorSet colorSet; graphToEps(graph, "coloring.eps"). title("Six Colored Plan Graph").copyright("(C) 2005 LEMON Project"). coords(coords).nodeColors(composeMap(colorSet, color)). nodeScale(5.0).scaleToA4().run(); return 0; }