diff -r d8475431bbbb -r 8e85e6bbefdf src/demo/coloring.cc --- a/src/demo/coloring.cc Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,71 +0,0 @@ -#include - -#include -#include -#include -#include - -using namespace std; -using namespace lemon; - -int main() { - typedef UndirSmartGraph Graph; - typedef Graph::Node Node; - typedef Graph::NodeIt NodeIt; - typedef Graph::UndirEdge UndirEdge; - typedef Graph::IncEdgeIt IncEdgeIt; - - Graph graph; - - UndirGraphReader reader(std::cin, graph); - Graph::NodeMap > coords(graph); - reader.readNodeMap("coords", coords); - - reader.run(); - - Graph::NodeMap color(graph, -2); - - Graph::NodeMap heapMap(graph, -1); - BinHeap > heap(heapMap); - - for (NodeIt it(graph); it != INVALID; ++it) { - heap.push(it, countOutEdges(graph, it)); - } - - vector order; - - while (!heap.empty()) { - Node node = heap.top(); - heap.pop(); - color[node] = -1; - order.push_back(node); - for (IncEdgeIt it(graph, node); it != INVALID; ++it) { - Node target = graph.runningNode(it); - if (color[target] == -2) { - heap.decrease(target, heap[target] - 1); - } - } - } - - for (int i = order.size() - 1; i >= 0; --i) { - set forbidden; - for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) { - Node target = graph.runningNode(it); - if (color[target] != -1) { - forbidden.insert(color[target]); - } - } - int current = 0; - while (forbidden.find(current) != forbidden.end()) ++current; - color[order[i]] = current; - } - - ColorSet colorSet; - - graphToEps(graph, "six_coloring.eps"). - title("Six Colored Graph").copyright("(C) 2005 LEMON Project"). - coords(coords).nodeColors(composeMap(colorSet, color)). - scaleToA4().run(); - - return 0; -}