1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/demo/coloring.cc Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,71 @@
1.4 +#include <vector>
1.5 +
1.6 +#include <lemon/smart_graph.h>
1.7 +#include <lemon/bin_heap.h>
1.8 +#include <lemon/graph_reader.h>
1.9 +#include <lemon/graph_to_eps.h>
1.10 +
1.11 +using namespace std;
1.12 +using namespace lemon;
1.13 +
1.14 +int main() {
1.15 + typedef UndirSmartGraph Graph;
1.16 + typedef Graph::Node Node;
1.17 + typedef Graph::NodeIt NodeIt;
1.18 + typedef Graph::UndirEdge UndirEdge;
1.19 + typedef Graph::IncEdgeIt IncEdgeIt;
1.20 +
1.21 + Graph graph;
1.22 +
1.23 + UndirGraphReader<Graph> reader(std::cin, graph);
1.24 + Graph::NodeMap<xy<double> > coords(graph);
1.25 + reader.readNodeMap("coords", coords);
1.26 +
1.27 + reader.run();
1.28 +
1.29 + Graph::NodeMap<int> color(graph, -2);
1.30 +
1.31 + Graph::NodeMap<int> heapMap(graph, -1);
1.32 + BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
1.33 +
1.34 + for (NodeIt it(graph); it != INVALID; ++it) {
1.35 + heap.push(it, countOutEdges(graph, it));
1.36 + }
1.37 +
1.38 + vector<Node> order;
1.39 +
1.40 + while (!heap.empty()) {
1.41 + Node node = heap.top();
1.42 + heap.pop();
1.43 + color[node] = -1;
1.44 + order.push_back(node);
1.45 + for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
1.46 + Node target = graph.runningNode(it);
1.47 + if (color[target] == -2) {
1.48 + heap.decrease(target, heap[target] - 1);
1.49 + }
1.50 + }
1.51 + }
1.52 +
1.53 + for (int i = order.size() - 1; i >= 0; --i) {
1.54 + set<int> forbidden;
1.55 + for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
1.56 + Node target = graph.runningNode(it);
1.57 + if (color[target] != -1) {
1.58 + forbidden.insert(color[target]);
1.59 + }
1.60 + }
1.61 + int current = 0;
1.62 + while (forbidden.find(current) != forbidden.end()) ++current;
1.63 + color[order[i]] = current;
1.64 + }
1.65 +
1.66 + ColorSet colorSet;
1.67 +
1.68 + graphToEps(graph, "six_coloring.eps").
1.69 + title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
1.70 + coords(coords).nodeColors(composeMap(colorSet, color)).
1.71 + scaleToA4().run();
1.72 +
1.73 + return 0;
1.74 +}