OKlibrary  0.2.1.6
GreedyColouring.hpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 15.12.2006 (Swansea)
00002 /* Copyright 2006 - 2007 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00015 #ifndef GREEDYCOLOURING_hHHbswtT6t4
00016 #define GREEDYCOLOURING_hHHbswtT6t4
00017 
00018 #include <functional>
00019 #include <ostream>
00020 #include <utility>
00021 #include <vector>
00022 #include <algorithm>
00023 #include <numeric>
00024 #include <cassert>
00025 
00026 #include <boost/graph/sequential_vertex_coloring.hpp>
00027 #include <boost/iterator/counting_iterator.hpp>
00028 #include <boost/property_map/property_map.hpp>
00029 
00030 #include <OKlib/General/Combinatorics.hpp>
00031 
00032 namespace OKlib {
00033   namespace HypergraphColouring {
00034 
00040     template <class Graph>
00041     struct Out_degree_order : std::binary_function<typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertex_descriptor, bool> {
00042       typedef Graph graph_type;
00043       typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
00044       const graph_type& g;
00045       explicit Out_degree_order(const graph_type& g) : g(g) {}
00046       bool operator ()(const vertex_descriptor a, const vertex_descriptor b) {
00047         return out_degree(a, g) < out_degree(b, g);
00048       }
00049     };
00050 
00052     template <class Graph>
00053     void output_vertex_degrees(const Graph& g, std::ostream& out) {
00054       typedef typename boost::graph_traits<Graph>::vertex_iterator vertex_iterator;
00055       typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
00056       const vertex_range& r(vertices(g));
00057       const vertex_iterator& end(r.second);
00058       for (vertex_iterator i = r.first; i != end; ++i)
00059         out << get(boost::vertex_name, g, *i) << " : " << out_degree(*i, g) << "\n";
00060     }
00061 
00067     template <class UndirectedGraph>
00068     struct Greedy_colouring {
00069 
00070       typedef UndirectedGraph graph_type;
00071 
00072       typedef typename boost::graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
00073       typedef typename boost::graph_traits<graph_type>::vertices_size_type vertices_size_type;
00074       typedef typename boost::graph_traits<graph_type>::vertex_iterator vertex_iterator;
00075 
00077       typedef typename boost::property_map<graph_type, boost::vertex_index_t>::const_type vertex_index_map;
00078       typedef typename boost::property_traits<vertex_index_map>::value_type vertex_index_type;
00079 
00080       typedef std::vector<vertex_descriptor> VertexVector;
00081       typedef std::pair<vertex_iterator, vertex_iterator> VertexRange;
00082 
00083       const graph_type& g;
00084       const vertices_size_type n;
00085 
00086       typedef ::OKlib::HypergraphColouring::Out_degree_order<graph_type> sort_type;
00087       sort_type sort;
00088 
00089       typedef unsigned long int count_type;
00090       typedef std::vector<count_type> hash_vector_type;
00092       hash_vector_type hash_orders;
00093 
00095       const VertexVector given_order;
00096   
00097       VertexVector optimal_order, worst_order;
00098 
00099       typedef vertices_size_type colour_type;
00101       typedef boost::iterator_property_map<colour_type*, vertex_index_map> colour_map_type;
00102 
00104       typedef std::vector<colour_type> colour_vector_type;
00105 
00107       colour_vector_type colour_vec;
00109       colour_map_type running_colour;
00110       // number of colours used by running_colour
00111       colour_type num_colours;
00112 
00114       colour_vector_type optimal_colouring, worst_colouring;
00115       colour_type min_colours, max_colours;
00116 
00118       VertexVector running_order;
00119 
00121       typedef typename VertexVector::size_type order_index_type;
00123       typedef std::vector<order_index_type> permutation_type;
00124 
00125       // ----------------------------------------------------------------------
00126 
00128       explicit Greedy_colouring(const graph_type& g) :
00129         g(g),
00130         n(checked_size(g)),
00131         sort(g),
00132         hash_orders(n+1),
00133         given_order(vertices(g).first, vertices(g).second),
00134         colour_vec(n),
00135         running_colour(&colour_vec.front(), get(boost::vertex_index, g)),
00136         min_colours(n+1),
00137         max_colours(0),
00138         running_order(n)
00139       {}
00140 
00141       void evaluation() {
00142         permutation_type permutation(boost::counting_iterator<order_index_type>(0), boost::counting_iterator<order_index_type>(n));
00143         do {
00144           set_order(permutation);
00145           colouring();
00146           assert(num_colours <= n);
00147           if (num_colours < min_colours) {
00148             optimal_colouring = colour_vec; min_colours = num_colours; optimal_order = running_order;
00149           }
00150           else if (num_colours > max_colours) {
00151             worst_colouring = colour_vec; max_colours =num_colours; worst_order = running_order;
00152           }
00153           ++hash_orders[num_colours];
00154         } while (std::next_permutation(permutation.begin(), permutation.end()));
00155         assert(optimal_order.size() == n);
00156         assert(optimal_colouring.size() == n);
00157         assert(worst_order.size() == n);
00158         assert(worst_colouring.size() == n);
00159         assert(std::accumulate(hash_orders.begin(), hash_orders.end(), (count_type)0) == Combinatorics::factorial(n));
00160       }
00161       
00162       void set_order(const permutation_type& p) {
00163         for (order_index_type i = 0; i != n; ++i) {
00164           assert(p[i] < n);
00165           running_order[i] = given_order[p[i]];
00166         }
00167       }
00168       void colouring() {
00169         num_colours = sequential_vertex_coloring(g, &running_order[0], running_colour);
00170       }
00171       
00172     private :
00173       
00174       vertices_size_type checked_size(const graph_type& g) {
00175         const vertices_size_type n(num_vertices(g));
00176         assert(n > 0);
00177         return n;
00178       }
00179       
00180     };
00181 
00182   }
00183 }
00184 
00185 #endif