Re: [Boost-users] PropertyGraphConcept concept checking errors for an example implicit graph

Subject: Re: [Boost-users] PropertyGraphConcept concept checking errors for an example implicit graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-06-24 18:33:54

On Thu, 24 Jun 2010, W.P. McNeill wrote:

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

You need a few more categories here: incidence_graph_tag, 
vertex_list_graph_tag, probably edge_list_graph_tag.  Write an empty 
struct that inherits from all of the ones that you are going to model.

> // AdjacencyGraph concept
> typedef RingAdjacencyIterator adjacency_iterator;
> 
> // PropertyGraph concept
> typedef boost::edge_weight_t edge_property_type;

Try changing this to:
typedef
    boost::property<boost::edge_weight_t, EdgeWeight>
    edge_property_type;

You can also specialize boost::property_map directly, which might be 
simpler.  Eventually, you will probably need to add a vertex_index 
property as well since many algorithms become much more difficult to use 
without one.

> // 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;

You are going to want to model at least VertexListGraph and IncidenceGraph 
(meaning you need to fill in most of these iterators with real types). 
AdjacencyGraph is not used by too many algorithms; IncidenceGraph is the 
important concept for traversal algorithms.

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

I don't know where it is coming from either.  See if changing 
edge_property_type fixes this.

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

It looks like the PropertyGraph concept requires that the property is 
read-write, so you should not check against that concept.  It looks like 
the ReadablePropertyGraph concept may do what you want.

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

If your property map is read-only and you don't care about whether the 
graph is const, just replace the versions of get() you had above (that 
took ImplicitRingGraph&) with ones that take const ImplicitRingGraph&.

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

You might also want to look at <boost/graph/grid_graph.hpp>.  This is an 
implicit n-dimensional grid graph.  It is fairly simple and was written 
recently so it is cleaner than adjacency_list or the other graph types 
(that have user-defined properties, etc. and so are complicated).

-- Jeremiah Willcock