demo/coloring.cc
author alpar
Thu, 14 Jul 2005 12:23:15 +0000
changeset 1557 3e8d928e283d
parent 1422 469b3f628dd1
child 1560 01707a8a4ca6
permissions -rw-r--r--
Each version of Kruskal is called the same ( kruskal(g,in,out) ) independently
from the input source and the output type.
     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 using namespace std;
     9 using namespace lemon;
    10 
    11 int 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 }