Boost logo

Boost Users :

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.



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net