OKlibrary  0.2.1.6
GreedyColouring.cpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 24.11.2006 (Swansea)
00002 /* Copyright 2006 - 2007, 2010 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 
00025 #include <iostream>
00026 #include <cassert>
00027 #include <string>
00028 #include <map>
00029 
00030 #include <boost/graph/adjacency_list.hpp>
00031 #include <boost/graph/graphviz.hpp>
00032 #include <boost/property_map/dynamic_property_map.hpp>
00033 
00034 
00035 #include <OKlib/Combinatorics/Hypergraphs/Colourings/GreedyColouring.hpp>
00036 
00037 int main(const int argc, const char* const argv[]) {
00038 
00040   typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, std::string> > UndirectedGraph;
00041   typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_type;
00042   typedef boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type;
00043   typedef boost::graph_traits<UndirectedGraph>::edges_size_type edges_size_type;
00044 
00045   UndirectedGraph g;
00046   {
00047     boost::dynamic_properties p;
00048     p.property("node_id", get(boost::vertex_name, g));
00049     boost::read_graphviz(std::cin, g, p);
00050   }
00051   
00052   const vertices_size_type n = num_vertices(g);
00053   const edges_size_type m = num_edges(g);
00054   
00055   std::cout << "\n" << n << ", " << m << std::endl;
00056   OKlib::HypergraphColouring::output_vertex_degrees(g, std::cout);
00057   std::cout << std::endl;
00058 
00059   OKlib::HypergraphColouring::Greedy_colouring<UndirectedGraph> fgg(g);
00060   assert(fgg.n == n);
00061 
00062   {
00063     typedef std::map<std::string, vertex_type> name_map_type;
00064     name_map_type map;
00065     for (vertices_size_type i = 0; i < n; ++i)
00066       map.insert(std::make_pair(get(boost::vertex_name, g, fgg.given_order[i]), fgg.given_order[i]));
00067     assert(map.size() == n);
00068     typedef name_map_type::const_iterator iterator;
00069     const iterator end(map.end());
00070     vertices_size_type i = 0;
00071     for (iterator j(map.begin()); j != end; ++i, ++j)
00072       fgg.running_order[i] = j -> second;
00073   }
00074   fgg.colouring();
00075   std::cout << "lexicographical order = " << fgg.num_colours << std::endl;
00076   for (vertices_size_type i = 0; i < n; ++i)
00077     std::cout << get(boost::vertex_name, g, fgg.running_order[i]) << " ";
00078   std::cout << std::endl;
00079   for (vertices_size_type i = 0; i < n; ++i)
00080     std::cout << get(boost::vertex_name, g, fgg.running_order[i]) << " -> " << fgg.colour_vec[get(boost::vertex_index, g, fgg.running_order[i])] << ", ";
00081   std::cout << std::endl;
00082   
00083   std::stable_sort(fgg.running_order.begin(), fgg.running_order.end(), fgg.sort);
00084   fgg.colouring();
00085   std::cout << "smallest degrees first = " << fgg.num_colours << std::endl;
00086   for (vertices_size_type i = 0; i < n; ++i)
00087     std::cout << get(boost::vertex_name, g, fgg.running_order[i]) << " ";
00088   std::cout << std::endl;
00089   for (vertices_size_type i = 0; i < n; ++i)
00090     std::cout << get(boost::vertex_name, g, fgg.running_order[i]) << " -> " << fgg.colour_vec[get(boost::vertex_index, g, fgg.running_order[i])] << ", ";
00091   std::cout << std::endl;
00092   
00093   std::reverse(fgg.running_order.begin(), fgg.running_order.end());
00094   fgg.colouring();
00095   std::cout << "largest degrees first = " << fgg.num_colours << std::endl;
00096   for (vertices_size_type i = 0; i < n; ++i)
00097     std::cout << get(boost::vertex_name, g, fgg.running_order[i]) << " ";
00098   std::cout << std::endl;
00099   for (vertices_size_type i = 0; i < n; ++i)
00100     std::cout << get(boost::vertex_name, g, fgg.running_order[i]) << " -> " << fgg.colour_vec[get(boost::vertex_index, g, fgg.running_order[i])] << ", ";
00101   std::cout << std::endl;
00102   
00103   if (argc > 1) {
00104     fgg.evaluation();
00105 
00106     std::cout << "\n";
00107     for (vertices_size_type i = 0; i <= n; ++i)
00108       std::cout << i << " : " << fgg.hash_orders[i] << "\n";
00109     std::cout << std::endl;
00110     
00111     std::cout << "min numbers of colours = " << fgg.min_colours << std::endl;
00112     for (vertices_size_type i = 0; i < n; ++i)
00113       std::cout << get(boost::vertex_name, g, fgg.optimal_order[i]) << " ";
00114     std::cout << std::endl;
00115     for (vertices_size_type i = 0; i < n; ++i)
00116       std::cout <<  get(boost::vertex_name, g, fgg.optimal_order[i]) << " -> " << fgg.optimal_colouring[get(boost::vertex_index, g, fgg.optimal_order[i])] << ", ";
00117     std::cout << std::endl;
00118     
00119     std::cout << "max number of colours = " << fgg.max_colours << std::endl;
00120     for (vertices_size_type i = 0; i < n; ++i)
00121       std::cout <<  get(boost::vertex_name, g, fgg.worst_order[i]) << " ";
00122     std::cout << std::endl;
00123     for (vertices_size_type i = 0; i < n; ++i)
00124       std::cout << get(boost::vertex_name, g, fgg.worst_order[i]) << " -> " << fgg.worst_colouring[get(boost::vertex_index, g, fgg.worst_order[i])] << ", ";
00125     std::cout << std::endl;
00126   }
00127 
00128 }
00129