demo/coloring.cc
author deba
Wed, 01 Mar 2006 10:25:30 +0000
changeset 1991 d7442141d9ef
parent 1956 a055123339d5
child 2038 33db14058543
permissions -rw-r--r--
The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.

The ResGraphAdaptor is based on this composition.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup demos
    20 ///\file
    21 ///\brief Coloring of a graph.
    22 ///
    23 /// This example shows how can we color the nodes of a planar graph efficiently
    24 /// with six colors.
    25 ///
    26 /// \include coloring.cc
    27 
    28 #include <vector>
    29 
    30 #include <iostream>
    31 
    32 #include <lemon/smart_graph.h>
    33 #include <lemon/linear_heap.h>
    34 #include <lemon/graph_reader.h>
    35 #include <lemon/graph_to_eps.h>
    36 
    37 #include <fstream>
    38 
    39 
    40 using namespace std;
    41 using namespace lemon;
    42 
    43 int main() {
    44 
    45   typedef SmartUGraph Graph;
    46   typedef Graph::Node Node;
    47   typedef Graph::NodeIt NodeIt;
    48   typedef Graph::UEdge UEdge;
    49   typedef Graph::IncEdgeIt IncEdgeIt;
    50 
    51   std::cout << "Six coloring of a planar graph" << std::endl;
    52   std::cout << "Input file: coloring.lgf" << std::endl;
    53   std::cout << "Output file: coloring.eps" << std::endl;
    54 
    55   Graph graph;
    56 
    57   UGraphReader<Graph> reader("coloring.lgf", graph);
    58   Graph::NodeMap<xy<double> > coords(graph);
    59   reader.readNodeMap("coords", coords);
    60   
    61   reader.run();
    62 
    63   Graph::NodeMap<int> color(graph, -2);
    64   
    65   Graph::NodeMap<int> heapMap(graph, -1);
    66   LinearHeap<Node, Graph::NodeMap<int> > heap(heapMap);
    67   
    68   for (NodeIt it(graph); it != INVALID; ++it) {
    69     heap.push(it, countOutEdges(graph, it));
    70   }
    71 
    72   vector<Node> order;
    73 
    74   while (!heap.empty()) {
    75     Node node = heap.top();
    76     heap.pop();
    77     color[node] = -1;
    78     order.push_back(node);
    79     for (IncEdgeIt it(graph, node); it != INVALID; ++it) {
    80       Node target = graph.runningNode(it); 
    81       if (color[target] == -2) {
    82 	heap.decrease(target, heap[target] - 1);
    83       }
    84     }
    85   }
    86 
    87   for (int i = order.size() - 1; i >= 0; --i) {
    88     set<int> forbidden;
    89     for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {
    90       Node target = graph.runningNode(it); 
    91       if (color[target] != -1) {
    92 	forbidden.insert(color[target]);
    93       }
    94     }
    95     int current = 0;
    96     while (forbidden.find(current) != forbidden.end()) ++current;
    97     color[order[i]] = current;
    98   }
    99 
   100   ColorSet colorSet;
   101 
   102   graphToEps(graph, "coloring.eps").
   103     title("Six Colored Plan Graph").copyright("(C) 2006 LEMON Project").
   104     coords(coords).nodeColors(composeMap(colorSet, color)).
   105     nodeScale(5.0).scaleToA4().run();
   106 
   107   return 0;
   108 }