COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/coloring.cc @ 1852:ffa7c6e96330

Last change on this file since 1852:ffa7c6e96330 was 1727:0c7d717b9538, checked in by Balazs Dezso, 18 years ago

Doc and changing heap

File size: 2.7 KB
Line 
1/* -*- C++ -*-
2 * demo/coloring.cc - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
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.
10 *
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
13 * purpose.
14 *
15 */
16
17///\ingroup demos
18///\file
19///\brief Coloring of a graph.
20///
21/// This example shows how can we color the nodes of a plan graph efficiently
22/// with six colors.
23///
24/// \include coloring.cc
25
26#include <vector>
27
28#include <iostream>
29
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>
34
35#include <fstream>
36
37
38using namespace std;
39using namespace lemon;
40
41int main() {
42
43  typedef UndirSmartGraph Graph;
44  typedef Graph::Node Node;
45  typedef Graph::NodeIt NodeIt;
46  typedef Graph::UndirEdge UndirEdge;
47  typedef Graph::IncEdgeIt IncEdgeIt;
48
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;
52
53  Graph graph;
54
55  UndirGraphReader<Graph> reader("coloring.lgf", graph);
56  Graph::NodeMap<xy<double> > coords(graph);
57  reader.readNodeMap("coords", coords);
58 
59  reader.run();
60
61  Graph::NodeMap<int> color(graph, -2);
62 
63  Graph::NodeMap<int> heapMap(graph, -1);
64  LinearHeap<Node, Graph::NodeMap<int> > heap(heapMap);
65 
66  for (NodeIt it(graph); it != INVALID; ++it) {
67    heap.push(it, countOutEdges(graph, it));
68  }
69
70  vector<Node> order;
71
72  while (!heap.empty()) {
73    Node node = heap.top();
74    heap.pop();
75    color[node] = -1;
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);
81      }
82    }
83  }
84
85  for (int i = order.size() - 1; i >= 0; --i) {
86    set<int> forbidden;
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]);
91      }
92    }
93    int current = 0;
94    while (forbidden.find(current) != forbidden.end()) ++current;
95    color[order[i]] = current;
96  }
97
98  ColorSet colorSet;
99
100  graphToEps(graph, "coloring.eps").
101    title("Six Colored Plan Graph").copyright("(C) 2005 LEMON Project").
102    coords(coords).nodeColors(composeMap(colorSet, color)).
103    nodeScale(5.0).scaleToA4().run();
104
105  return 0;
106}
Note: See TracBrowser for help on using the repository browser.