COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/coloring.cc @ 1683:13648409b596

Last change on this file since 1683:13648409b596 was 1683:13648409b596, checked in by Balazs Dezso, 19 years ago

Input file for coloring.

File size: 2.5 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#include <vector>
18
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>
23
24#include <fstream>
25#include <iostream>
26
27
28using namespace std;
29using namespace lemon;
30
31int main() {
32
33  typedef UndirSmartGraph Graph;
34  typedef Graph::Node Node;
35  typedef Graph::NodeIt NodeIt;
36  typedef Graph::UndirEdge UndirEdge;
37  typedef Graph::IncEdgeIt IncEdgeIt;
38
39  std::cout << "Six coloring of a plan graph" << std::endl;
40  std::cout << "Input file: coloring.lgf" << std::endl;
41  std::cout << "Output file: coloring.eps" << std::endl;
42
43  Graph graph;
44
45  UndirGraphReader<Graph> reader("coloring.lgf", graph);
46  Graph::NodeMap<xy<double> > coords(graph);
47  reader.readNodeMap("coords", coords);
48 
49  reader.run();
50
51  Graph::NodeMap<int> color(graph, -2);
52 
53  Graph::NodeMap<int> heapMap(graph, -1);
54  BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
55 
56  for (NodeIt it(graph); it != INVALID; ++it) {
57    heap.push(it, countOutEdges(graph, it));
58  }
59
60  vector<Node> order;
61
62  while (!heap.empty()) {
63    Node node = heap.top();
64    heap.pop();
65    color[node] = -1;
66    order.push_back(node);
67    for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
68      Node target = graph.runningNode(it);
69      if (color[target] == -2) {
70        heap.decrease(target, heap[target] - 1);
71      }
72    }
73  }
74
75  for (int i = order.size() - 1; i >= 0; --i) {
76    set<int> forbidden;
77    for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
78      Node target = graph.runningNode(it);
79      if (color[target] != -1) {
80        forbidden.insert(color[target]);
81      }
82    }
83    int current = 0;
84    while (forbidden.find(current) != forbidden.end()) ++current;
85    color[order[i]] = current;
86  }
87
88  ColorSet colorSet;
89
90  graphToEps(graph, "coloring.eps").
91    title("Six Colored Plan Graph").copyright("(C) 2005 LEMON Project").
92    coords(coords).nodeColors(composeMap(colorSet, color)).
93    nodeScale(5.0).scaleToA4().run();
94
95  return 0;
96}
Note: See TracBrowser for help on using the repository browser.