[NEWBIE] [BGL] Compile error while using greedy graph coloring example v1.47.0
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.
On Sun, 21 Aug 2011, Ragavendran Gopalakrishnan wrote:
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.
Those parts of the code are designed to check for usage errors of the algorithm, but the second and third of them are incorrect. You also pass a pointer to an std::map into your algorithm, rather than turning it into a property map using make_assoc_property_map. I have attached a corrected version of the code; you might want to diff it against your version to see what's been changed. -- Jeremiah Willcock
participants (2)
-
Jeremiah Willcock
-
Ragavendran Gopalakrishnan