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.... 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.... 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.