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.