COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/coloring.cc @ 1578:1d3a1bcbc874

Last change on this file since 1578:1d3a1bcbc874 was 1577:15098fb5275c, checked in by athos, 19 years ago

Documentation (lp_demo,lp_maxflow) and slight changes (rest).

File size: 2.1 KB
Line 
1#include <vector>
2
3#include <lemon/smart_graph.h>
4#include <lemon/bin_heap.h>
5#include <lemon/graph_reader.h>
6#include <lemon/graph_to_eps.h>
7
8#include <fstream>
9#include <iostream>
10
11
12using namespace std;
13using namespace lemon;
14
15int main(int argc, char *argv[])
16{
17  if(argc<2)
18  {
19      std::cerr << "USAGE: coloring input_file.lgf" << std::endl;
20      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;
21      return 0;
22  }
23
24
25  //input stream to read the graph from
26  std::ifstream is(argv[1]);
27
28  typedef UndirSmartGraph Graph;
29  typedef Graph::Node Node;
30  typedef Graph::NodeIt NodeIt;
31  typedef Graph::UndirEdge UndirEdge;
32  typedef Graph::IncEdgeIt IncEdgeIt;
33
34  Graph graph;
35
36  UndirGraphReader<Graph> reader(is, graph);
37  Graph::NodeMap<xy<double> > coords(graph);
38  reader.readNodeMap("coords", coords);
39 
40  reader.run();
41
42  Graph::NodeMap<int> color(graph, -2);
43 
44  Graph::NodeMap<int> heapMap(graph, -1);
45  BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
46 
47  for (NodeIt it(graph); it != INVALID; ++it) {
48    heap.push(it, countOutEdges(graph, it));
49  }
50
51  vector<Node> order;
52
53  while (!heap.empty()) {
54    Node node = heap.top();
55    heap.pop();
56    color[node] = -1;
57    order.push_back(node);
58    for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
59      Node target = graph.runningNode(it);
60      if (color[target] == -2) {
61        heap.decrease(target, heap[target] - 1);
62      }
63    }
64  }
65
66  for (int i = order.size() - 1; i >= 0; --i) {
67    set<int> forbidden;
68    for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
69      Node target = graph.runningNode(it);
70      if (color[target] != -1) {
71        forbidden.insert(color[target]);
72      }
73    }
74    int current = 0;
75    while (forbidden.find(current) != forbidden.end()) ++current;
76    color[order[i]] = current;
77  }
78
79  ColorSet colorSet;
80
81  graphToEps(graph, "six_coloring.eps").
82    title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
83    coords(coords).nodeColors(composeMap(colorSet, color)).
84    scaleToA4().run();
85
86  return 0;
87}
Note: See TracBrowser for help on using the repository browser.