I am writing a stripped-down implicit graph that I hope can be a useful template for others working with the Boost Graph library. The project is hosted at github. Excerpts from the source are in this email, and the full source is viewable online at http://github.com/wpm/Boost-Implicit-Graph-Example.

I am currently getting errors from the concept checking code which I don't understand and am looking for suggestions as to what I am doing wrong.

This is graph class.

struct ImplicitRingGraph {

ImplicitRingGraph(size_t n):n(n) {};

// Graph concept

typedef size_t vertex_descriptor;

typedef boost::undirected_tag directed_category;

typedef boost::disallow_parallel_edge_tag edge_parallel_category;

typedef boost::adjacency_graph_tag traversal_category;

// AdjacencyGraph concept

typedef RingAdjacencyIterator adjacency_iterator;

// PropertyGraph concept

typedef boost::edge_weight_t edge_property_type;

// Additional types required by the concept-checking code.

typedef std::pair<vertex_descriptor, vertex_descriptor> edge_descriptor;

typedef size_t vertices_size_type;

typedef size_t edges_size_type;

typedef size_t degree_size_type;

typedef void out_edge_iterator;

typedef void in_edge_iterator;

typedef void vertex_iterator;

typedef void edge_iterator;

// The number of vertices in the graph.

size_t n;

};

typedef boost::graph_traits<ImplicitRingGraph>::edge_descriptor Edge;

I want the edges to have weights, so it models the PropertyGraph concept. The following functions implement the valid expressions.

EdgeWeightMap get(boost::edge_weight_t, ImplicitRingGraph& g) {

return EdgeWeightMap();

}

EdgeWeight get(boost::edge_weight_t tag, ImplicitRingGraph& g, Edge e) {

return get(tag, g)[e];

}

(Definitions of Edge, EdgeWeight, and EdgeWeightMap are visible online. I also define an adjacency iterator that is not shown here.)

I can write code that reads an edge weight.

ImplicitRingGraph g(5);

EdgeWeightMap m = get(boost::edge_weight, g);

boost::graph_traits<ImplicitRingGraph>::edge_descriptor e(0, 1);

EdgeWeight w = get(boost::edge_weight, g, e);

However I get errors when I try to use the concept checking code.

function_requires<

PropertyGraphConcept<ImplicitRingGraph,

Edge,

edge_weight_t>

>();

The full error printout is huge, but there appear to be three relevant problems.

1. graph_concepts.hpp:406: error: conversion from ‘EdgeWeightMap’ to non-scalar type ‘boost::typed_identity_property_map<size_t>’ requested

The line in graph_concepts.hpp is

Map pmap = get(Property(), g);

inside the concept check for PropertyGraph. It looks to me like I have a function to handle this. I don't understand where boost::typed_identity_property_map<size_t> is coming from.

2. graph_concepts.hpp:408: error: no matching function for call to ‘put(boost::edge_weight_t, ImplicitRingGraph&, Edge&, size_t&)’

I didn't write any put() functions so I understand why I'm getting this. However, I would like the edge weights to be readable but not writeable (myEdgeWeightMap models a ReadablePropertyMap), and I can't figure out how to specify the read-only property in the graph defintion.

3. graph_concepts.hpp:390: error: no matching function for call to ‘get(boost::edge_weight_t, const ImplicitRingGraph&)’

graph_concepts.hpp:391: error: no matching function for call to ‘get(boost::edge_weight_t, const ImplicitRingGraph&, Edge&)’

Should I create functions identical to what I've already written, except with constant modifiers in front of the graph type? That feels like redundant source.

Thanks for any help you can give. Hopefully, a completed version of this example would be a useful resource for other BGL developers.