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