COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/coloring.cc @ 1636:260ac104190f

Last change on this file since 1636:260ac104190f was 1636:260ac104190f, checked in by Akos Ladanyi, 19 years ago

Added missing copyright headers, and corrected the file names in some of them.

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#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(int argc, char *argv[])
32{
33  if(argc<2)
34  {
35      std::cerr << "USAGE: coloring input_file.lgf" << std::endl;
36      std::cerr << "The file 'input_file.lgf' has to contain a graph in LEMON format together with a nodemap called 'coords' to draw the graph (e.g. sample.lgf is not such a file)." << std::endl;
37      return 0;
38  }
39
40
41  //input stream to read the graph from
42  std::ifstream is(argv[1]);
43
44  typedef UndirSmartGraph Graph;
45  typedef Graph::Node Node;
46  typedef Graph::NodeIt NodeIt;
47  typedef Graph::UndirEdge UndirEdge;
48  typedef Graph::IncEdgeIt IncEdgeIt;
49
50  Graph graph;
51
52  UndirGraphReader<Graph> reader(is, graph);
53  Graph::NodeMap<xy<double> > coords(graph);
54  reader.readNodeMap("coords", coords);
55 
56  reader.run();
57
58  Graph::NodeMap<int> color(graph, -2);
59 
60  Graph::NodeMap<int> heapMap(graph, -1);
61  BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
62 
63  for (NodeIt it(graph); it != INVALID; ++it) {
64    heap.push(it, countOutEdges(graph, it));
65  }
66
67  vector<Node> order;
68
69  while (!heap.empty()) {
70    Node node = heap.top();
71    heap.pop();
72    color[node] = -1;
73    order.push_back(node);
74    for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
75      Node target = graph.runningNode(it);
76      if (color[target] == -2) {
77        heap.decrease(target, heap[target] - 1);
78      }
79    }
80  }
81
82  for (int i = order.size() - 1; i >= 0; --i) {
83    set<int> forbidden;
84    for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
85      Node target = graph.runningNode(it);
86      if (color[target] != -1) {
87        forbidden.insert(color[target]);
88      }
89    }
90    int current = 0;
91    while (forbidden.find(current) != forbidden.end()) ++current;
92    color[order[i]] = current;
93  }
94
95  ColorSet colorSet;
96
97  graphToEps(graph, "six_coloring.eps").
98    title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
99    coords(coords).nodeColors(composeMap(colorSet, color)).
100    scaleToA4().run();
101
102  return 0;
103}
Note: See TracBrowser for help on using the repository browser.