[Boost-users] [NEWBIE] [BGL] Compile error while using greedy graph coloring example v1.47.0

Subject: [Boost-users] [NEWBIE] [BGL] Compile error while using greedy graph coloring example v1.47.0
From: Ragavendran Gopalakrishnan (ragad_at_[hidden])
Date: 2011-08-21 20:25:06

Hello all,

I'm a newbie to using Boost Graph Libraries for my project. I was reading
the documentation, and tried implementing the greedy graph coloring
algorithm that is presented in the following webpage:
http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/constructing_algorithms.html

I get compile errors involving the following lines of code:

function_requires< IntegerConcept<ColorType> >();
function_requires< size_type, ReadablePropertyMapConcept<Order> >();
typedef typename same_type<OrderType, vertex_descriptor>::type req_same;

I understand that the first two function_requires calls are concept checks,
and I don't know what the use of the third line is, as req_same is never
used. Anyway, if I comment these three lines, my program compiles fine, and
works perfectly. I am unable to understand the errors and correct them.

Here is my source code (coloring.cc) - the only change I made from the
example algorithm is to pass color by reference, so that I can directly
access the resulting coloring.

001. #include <iostream>
002. #include <map>
003. #include <limits>
004. #include <boost/concept_check.hpp>
005. #include <boost/graph/graph_traits.hpp>
006. #include <boost/graph/graph_concepts.hpp>
007. #include <boost/graph/adjacency_matrix.hpp>
008. #include <boost/property_map/property_map.hpp>
009.
010. using namespace boost;
011.
012. // Example coloring function provided in BGL online documentation at
013. //
http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/constructing_algorithms.html
014. template <class VertexListGraph, class Order, class Color>
015. typename graph_traits<VertexListGraph>::vertices_size_type
016. sequential_vertex_color_ting (const VertexListGraph& G,
017.                               Order order, const Color& color) {
018.   typedef graph_traits<VertexListGraph> GraphTraits;
019.   typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
020.   typedef typename GraphTraits::vertices_size_type size_type;
021.   typedef typename property_traits<Color>::value_type ColorType;
022.   typedef typename property_traits<Order>::value_type OrderType;
023.
024.   function_requires< VertexListGraphConcept<VertexListGraph> >();
025.   function_requires< ReadWritePropertyMapConcept<Color,
vertex_descriptor> >();
026.   function_requires< IntegerConcept<ColorType> >();
027.   function_requires< size_type, ReadablePropertyMapConcept<Order> >();
028.   typedef typename same_type<OrderType, vertex_descriptor>::type
req_same;
029.
030.   size_type max_color = 0;
031.   const size_type V = num_vertices(G);
032.   std::vector<size_type> mark(V,
std::numeric_limits<size_type>::max());
033.
034.   typename GraphTraits::vertex_iterator v, vend;
035.   for (tie(v, vend) = vertices(G); v != vend ; v++) {
036.     (*color)[*v] = V-1; // which means "not colored"
037.   }
038.
039.   for (size_type i = 0 ; i < V ; i++) {
040.     vertex_descriptor current = order[i];
041.
042.     // mark all the colors of the adjacent vertices
043.     typename GraphTraits::adjacency_iterator ai, aend;
044.     for (tie(ai, aend) = adjacent_vertices(current, G) ; ai != aend ;
++ai) {
045.       mark[(*color)[*ai]] = i;
046.     }
047.
048.     // find the smallest color unused by the adjacent vertices
049.     size_type smallest_color = 0;
050.     while (smallest_color < max_color && mark[smallest_color] == i) {
051.       ++smallest_color;
052.     }
053.
054.     // if all the colors are used up, increase the number of colors
055.     if (smallest_color == max_color) {
056.       ++max_color;
057.     }
058.
059.     (*color)[current] = smallest_color;
060.   }
061.   return max_color;
062. }
063.
064. int main(int, char*[]) {
065.   // Create adjacency matrix for a star graph on 5 vertices
066.   int numberOfVertices = 5;
067.   int adjacencyMatrix[numberOfVertices][numberOfVertices];
068.   for (int i = 0 ; i < numberOfVertices ; i++) {
069.     for (int j = 0 ; j < numberOfVertices ; j++) {
070.       if ((i == 0)||(j == 0)&&(i != j)) {
071.         adjacencyMatrix[i][j] = 1;
072.       } else {
073.         adjacencyMatrix[i][j] = 0;
074.       }
075.     }
076.   }
077.
078.   // Construct boost graph
079.   typedef adjacency_matrix<undirectedS> UGraph;
080.   typedef graph_traits<UGraph> GraphTraits;
081.   typedef GraphTraits::vertex_descriptor vertex_descriptor;
082.   typedef GraphTraits::vertex_iterator vertex_iterator;
083.   UGraph ug(numberOfVertices);
084.   for (int i = 0 ; i < numberOfVertices ; i++) {
085.     for (int j = i+1 ; j < numberOfVertices ; j++) {
086.       if (adjacencyMatrix[i][j] == 1) {
087.         add_edge(i,j,ug);
088.       }
089.     }
090.   }
091.
092.   // Create order as an externally stored property
093.   vertex_descriptor order[numberOfVertices];
094.   std::pair<vertex_iterator, vertex_iterator> p = vertices(ug);
095.   for (int i = 0 ; i < numberOfVertices ; i++) {
096.       order[i] = *(p.first + i);
097.   }
098.
099.   // Create color as an externally stored property
100.   std::map<vertex_descriptor, int> color;
101.   for (int i = 0 ; i < numberOfVertices ; i++) {
102.
color.insert(std::make_pair(vertex_descriptor(*(p.first+i)),int(0)));
103.   }
104.
105.   // Get the coloring
106.   sequential_vertex_color_ting(ug,order,&color);
107.
108.   // Display the coloring
109.   for (int i = 0 ; i < numberOfVertices ; i++) {
110.     std::cout << "Color of vertex " << i << " is " <<
color[*(p.first+i)] << std::endl;
111.   }
112.
113.   return 0;
114. }

The command I used to compile is (g++ version 4.4.3):

$ g++ -I ../../Desktop/boost_1_47_0/ coloring.cc

The compiler output is:

coloring.cc: In function ‘typename
boost::graph_traits<G>::vertices_size_type
sequential_vertex_color_ting(const VertexListGraph&, Order, const Color&)’:
coloring.cc:27: error: wrong number of template arguments (1, should be 2)
../../Desktop/boost_1_47_0/boost/property_map/property_map.hpp:191: error:
provided for ‘template<class PMap, class Key> struct
boost::ReadablePropertyMapConcept’
coloring.cc:28: error: expected nested-name-specifier before ‘same_type’
coloring.cc:28: error: expected initializer before ‘<’ token
In file included from coloring.cc:4:
../../Desktop/boost_1_47_0/boost/concept_check.hpp: In destructor
‘boost::Integer<T>::~Integer() [with T = std::map<long unsigned int, int,
std::less<long unsigned int>, std::allocator<std::pair<const long unsigned
int, int> > >]’:
../../Desktop/boost_1_47_0/boost/concept_check.hpp:65:   instantiated from
‘static void
boost::concepts::requirement<boost::concepts::failed************
Model::************>::failed() [with Model =
boost::IntegerConcept<std::map<long unsigned int, int, std::less<long
unsigned int>, std::allocator<std::pair<const long unsigned int, int> > >
>]’
../../Desktop/boost_1_47_0/boost/concept_check.hpp:45:   instantiated from
‘void boost::function_requires(Model*) [with Model =
boost::IntegerConcept<std::map<long unsigned int, int, std::less<long
unsigned int>, std::allocator<std::pair<const long unsigned int, int> > >
>]’
coloring.cc:26:   instantiated from ‘typename
boost::graph_traits<G>::vertices_size_type
sequential_vertex_color_ting(const VertexListGraph&, Order, const Color&)
[with VertexListGraph = main(int, char**)::UGraph, Order =
main::vertex_descriptor*, Color = std::map<long unsigned int, int,
std::less<long unsigned int>, std::allocator<std::pair<const long unsigned
int, int> > >*]’
coloring.cc:106:   instantiated from here
../../Desktop/boost_1_47_0/boost/concept_check.hpp:69: error: ‘class
std::map<long unsigned int, int, std::less<long unsigned int>,
std::allocator<std::pair<const long unsigned int, int> > >’ has no member
named ‘error_type_must_be_an_integer_type’

When I comment lines 26-28, the program compiles successfully and executing
a.out gives the following output, as expected:

Color of vertex 0 is 0
Color of vertex 1 is 1
Color of vertex 2 is 1
Color of vertex 3 is 1
Color of vertex 4 is 1

Please advise me on what the compiler errors mean. I did try digging into
some of the header files, but I couldn't find out what the mistake is.

Regards,
Raga.