COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/coloring.cc @ 2116:b6a68c15a6a3

Last change on this file since 2116:b6a68c15a6a3 was 2116:b6a68c15a6a3, checked in by Balazs Dezso, 17 years ago

Revert splitted files

File size: 2.7 KB
RevLine 
[1636]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1636]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
[1727]19///\ingroup demos
20///\file
21///\brief Coloring of a graph.
22///
[1959]23/// This example shows how can we color the nodes of a planar graph efficiently
[1727]24/// with six colors.
25///
26/// \include coloring.cc
27
[1422]28#include <vector>
29
[1727]30#include <iostream>
31
[2116]32#include <lemon/smart_graph.h>
[2038]33#include <lemon/bucket_heap.h>
[1422]34#include <lemon/graph_reader.h>
35#include <lemon/graph_to_eps.h>
36
[1560]37#include <fstream>
38
39
[1422]40using namespace std;
41using namespace lemon;
42
[1683]43int main() {
[1560]44
[1909]45  typedef SmartUGraph Graph;
[1422]46  typedef Graph::Node Node;
47  typedef Graph::NodeIt NodeIt;
[1909]48  typedef Graph::UEdge UEdge;
[1422]49  typedef Graph::IncEdgeIt IncEdgeIt;
50
[1959]51  std::cout << "Six coloring of a planar graph" << std::endl;
[1683]52  std::cout << "Input file: coloring.lgf" << std::endl;
53  std::cout << "Output file: coloring.eps" << std::endl;
54
[1422]55  Graph graph;
56
[1909]57  UGraphReader<Graph> reader("coloring.lgf", graph);
[1422]58  Graph::NodeMap<xy<double> > coords(graph);
59  reader.readNodeMap("coords", coords);
60 
61  reader.run();
62
63  Graph::NodeMap<int> color(graph, -2);
64 
65  Graph::NodeMap<int> heapMap(graph, -1);
[2038]66  BucketHeap<Node, Graph::NodeMap<int> > heap(heapMap);
[1422]67 
68  for (NodeIt it(graph); it != INVALID; ++it) {
69    heap.push(it, countOutEdges(graph, it));
70  }
71
72  vector<Node> order;
73
74  while (!heap.empty()) {
75    Node node = heap.top();
76    heap.pop();
77    color[node] = -1;
78    order.push_back(node);
79    for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
80      Node target = graph.runningNode(it);
81      if (color[target] == -2) {
82        heap.decrease(target, heap[target] - 1);
83      }
84    }
85  }
86
87  for (int i = order.size() - 1; i >= 0; --i) {
88    set<int> forbidden;
89    for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
90      Node target = graph.runningNode(it);
91      if (color[target] != -1) {
92        forbidden.insert(color[target]);
93      }
94    }
95    int current = 0;
96    while (forbidden.find(current) != forbidden.end()) ++current;
97    color[order[i]] = current;
98  }
99
100  ColorSet colorSet;
101
[1683]102  graphToEps(graph, "coloring.eps").
[1875]103    title("Six Colored Plan Graph").copyright("(C) 2006 LEMON Project").
[1422]104    coords(coords).nodeColors(composeMap(colorSet, color)).
[1683]105    nodeScale(5.0).scaleToA4().run();
[1422]106
107  return 0;
108}
Note: See TracBrowser for help on using the repository browser.