COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/coloring.cc @ 1523:144ab0e4b09c

Last change on this file since 1523:144ab0e4b09c was 1435:8e85e6bbefdf, checked in by Akos Ladanyi, 15 years ago

trunk/src/* move to trunk/

File size: 1.7 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
8using namespace std;
9using namespace lemon;
10
11int main() {
12  typedef UndirSmartGraph Graph;
13  typedef Graph::Node Node;
14  typedef Graph::NodeIt NodeIt;
15  typedef Graph::UndirEdge UndirEdge;
16  typedef Graph::IncEdgeIt IncEdgeIt;
17
18  Graph graph;
19
20  UndirGraphReader<Graph> reader(std::cin, graph);
21  Graph::NodeMap<xy<double> > coords(graph);
22  reader.readNodeMap("coords", coords);
23 
24  reader.run();
25
26  Graph::NodeMap<int> color(graph, -2);
27 
28  Graph::NodeMap<int> heapMap(graph, -1);
29  BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
30 
31  for (NodeIt it(graph); it != INVALID; ++it) {
32    heap.push(it, countOutEdges(graph, it));
33  }
34
35  vector<Node> order;
36
37  while (!heap.empty()) {
38    Node node = heap.top();
39    heap.pop();
40    color[node] = -1;
41    order.push_back(node);
42    for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
43      Node target = graph.runningNode(it);
44      if (color[target] == -2) {
45        heap.decrease(target, heap[target] - 1);
46      }
47    }
48  }
49
50  for (int i = order.size() - 1; i >= 0; --i) {
51    set<int> forbidden;
52    for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
53      Node target = graph.runningNode(it);
54      if (color[target] != -1) {
55        forbidden.insert(color[target]);
56      }
57    }
58    int current = 0;
59    while (forbidden.find(current) != forbidden.end()) ++current;
60    color[order[i]] = current;
61  }
62
63  ColorSet colorSet;
64
65  graphToEps(graph, "six_coloring.eps").
66    title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
67    coords(coords).nodeColors(composeMap(colorSet, color)).
68    scaleToA4().run();
69
70  return 0;
71}
Note: See TracBrowser for help on using the repository browser.