1.1 --- a/src/demo/Makefile.am	Sat May 14 17:39:37 2005 +0000
     1.2 +++ b/src/demo/Makefile.am	Sat May 14 17:40:45 2005 +0000
     1.3 @@ -8,7 +8,8 @@
     1.4  	dim_to_lgf \
     1.5  	graph_to_eps_demo \
     1.6  	min_route \
     1.7 -	sub_graph_adaptor_demo
     1.8 +	sub_graph_adaptor_demo \
     1.9 +	coloring
    1.10  
    1.11  if HAVE_GLPK
    1.12  noinst_PROGRAMS += lp_demo lp_maxflow_demo
    1.13 @@ -23,6 +24,8 @@
    1.14  
    1.15  dim_to_lgf_SOURCES = dim_to_lgf.cc
    1.16  
    1.17 +coloring_SOURCES = coloring.cc
    1.18 +
    1.19  graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
    1.20  
    1.21  min_route_SOURCES = min_route.cc

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/demo/coloring.cc	Sat May 14 17:40:45 2005 +0000
     2.3 @@ -0,0 +1,71 @@
     2.4 +#include <vector>
     2.5 +
     2.6 +#include <lemon/smart_graph.h>
     2.7 +#include <lemon/bin_heap.h>
     2.8 +#include <lemon/graph_reader.h>
     2.9 +#include <lemon/graph_to_eps.h>
    2.10 +
    2.11 +using namespace std;
    2.12 +using namespace lemon;
    2.13 +
    2.14 +int main() {
    2.15 +  typedef UndirSmartGraph Graph;
    2.16 +  typedef Graph::Node Node;
    2.17 +  typedef Graph::NodeIt NodeIt;
    2.18 +  typedef Graph::UndirEdge UndirEdge;
    2.19 +  typedef Graph::IncEdgeIt IncEdgeIt;
    2.20 +
    2.21 +  Graph graph;
    2.22 +
    2.23 +  UndirGraphReader<Graph> reader(std::cin, graph);
    2.24 +  Graph::NodeMap<xy<double> > coords(graph);
    2.25 +  reader.readNodeMap("coords", coords);
    2.26 +  
    2.27 +  reader.run();
    2.28 +
    2.29 +  Graph::NodeMap<int> color(graph, -2);
    2.30 +  
    2.31 +  Graph::NodeMap<int> heapMap(graph, -1);
    2.32 +  BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);
    2.33 +  
    2.34 +  for (NodeIt it(graph); it != INVALID; ++it) {
    2.35 +    heap.push(it, countOutEdges(graph, it));
    2.36 +  }
    2.37 +
    2.38 +  vector<Node> order;
    2.39 +
    2.40 +  while (!heap.empty()) {
    2.41 +    Node node = heap.top();
    2.42 +    heap.pop();
    2.43 +    color[node] = -1;
    2.44 +    order.push_back(node);
    2.45 +    for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
    2.46 +      Node target = graph.runningNode(it); 
    2.47 +      if (color[target] == -2) {
    2.48 +	heap.decrease(target, heap[target] - 1);
    2.49 +      }
    2.50 +    }
    2.51 +  }
    2.52 +
    2.53 +  for (int i = order.size() - 1; i >= 0; --i) {
    2.54 +    set<int> forbidden;
    2.55 +    for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
    2.56 +      Node target = graph.runningNode(it); 
    2.57 +      if (color[target] != -1) {
    2.58 +	forbidden.insert(color[target]);
    2.59 +      }
    2.60 +    }
    2.61 +    int current = 0;
    2.62 +    while (forbidden.find(current) != forbidden.end()) ++current;
    2.63 +    color[order[i]] = current;
    2.64 +  }
    2.65 +
    2.66 +  ColorSet colorSet;
    2.67 +
    2.68 +  graphToEps(graph, "six_coloring.eps").
    2.69 +    title("Six Colored Graph").copyright("(C) 2005 LEMON Project").
    2.70 +    coords(coords).nodeColors(composeMap(colorSet, color)).
    2.71 +    scaleToA4().run();
    2.72 +
    2.73 +  return 0;
    2.74 +}