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: W.P. McNeill (billmcn_at_[hidden])
Date: 2010-06-28 19:15:12

Take at look at the code up on
http://github.com/wpm/Boost-Implicit-Graph-Example.  Except for one
compilation problem described below, I think this is done and ready to be
included in an examples directory.

I have implemented all the non-mutable graph concepts and have an edge
weight property.  The main() function puts the graph through various paces
then runs Dijkstra's algorithm.

(I didn't model AdjacencyMatrix since the documentation indicates that this
isn't used by any Boost algorithms, though it would be easy enough to
implement.)

I decided not to implement a mutable vertex property map because I think
this example is easiest to understand if it focuses exclusively on immutable
graph concepts.  (Plus examples of how to create mutable vertex property
maps are already easy to locate online.)

My last bug is in the implementation of the AdjacencyGraph concept.  I'm
trying to use the Adjacency Iterator Adaptor.  When in the graph declaration
I replace:

    typedef void adjacency_iterator;

with

    typedef boost::adjacency_iterator_generator<graph>::type
      adjacency_iterator;

which I copied from the example in the online documentation I get a huge
error spew which starts like this:

g++ -g -I/opt/local/include -Wall -Werror -O3   -c -o main.o main.cpp
/opt/local/include/boost/graph/graph_traits.hpp: In instantiation of
‘boost::graph_traits<implicit_ring::graph>’:
implicit.hpp:113:   instantiated from here
/opt/local/include/boost/graph/graph_traits.hpp:31: error: no type named
‘adjacency_iterator’ in ‘class implicit_ring::graph’
/opt/local/include/boost/graph/graph_traits.hpp:34: error: no type named
‘vertex_iterator’ in ‘class implicit_ring::graph’
/opt/local/include/boost/graph/graph_traits.hpp:35: error: no type named
‘edge_iterator’ in ‘class implicit_ring::graph’
/opt/local/include/boost/graph/graph_traits.hpp:41: error: no type named
‘vertices_size_type’ in ‘class implicit_ring::graph’
/opt/local/include/boost/graph/graph_traits.hpp:42: error: no type named
‘edges_size_type’ in ‘class implicit_ring::graph’
/usr/include/c++/4.0.0/bits/stl_iterator_base_types.h: In instantiation of
‘std::iterator_traits<implicit_ring::ring_incident_edge_iterator>’:
/opt/local/include/boost/detail/iterator.hpp:83:   instantiated from
‘boost::detail::iterator_traits<implicit_ring::ring_incident_edge_iterator>’
/opt/local/include/boost/graph/adjacency_iterator.hpp:55:   instantiated
from ‘boost::adjacency_iterator_generator<implicit_ring::graph, size_t,
implicit_ring::ring_incident_edge_iterator>’
implicit.hpp:113:   instantiated from here
/usr/include/c++/4.0.0/bits/stl_iterator_base_types.h:129: error: invalid
use of undefined type ‘struct implicit_ring::ring_incident_edge_iterator’

The problem looks like unrecognized forward declarations of either the graph
or ring_incident_edge_iterator, but I do have forward declarations for
these.  Any ideas why this is failing.

On Sat, Jun 26, 2010 at 8:30 AM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Fri, 25 Jun 2010, W.P. McNeill wrote:
>
>  I'll look into implementing all the non-mutable graph concepts.  That
>> shouldn't be difficult.  Are the following concept are consistent with each
>> other?
>>  *  Graph
>>  *  IncidenceGraph
>>  *  BidirectionalGraph
>>  *  AdjacencyGraph
>>  *  VertexListGraph
>>  *  EdgeListGraph
>>  *  PropertyGraph
>> What should I specify for the traversal_category if I model all of them
>> with a single object?
>>
>
> I believe they are all consistent.  Your traversal category should inherit
> virtually from all of the tags for the concepts that your graph provides.
> See the part in <boost/graph/grid_graph.hpp> that first mentions "virtual"
> for an example.
>
>
>  I think also having a vertex property map is a good idea.  Maybe I'll make
>> that a mutable color map, so there's an example of a writable property map.
>>  Should I use associative_property_map as a base class?  (That's what's done
>> in "The Boost Graph Library" section 15.3.2.)
>>
>
> I would use iterator_property_map (on a vector) with the vertex_index map
> that you have/are going to put in.
>
>
>  I'll add Dijkstra's algorithm to the main() function.
>>
>
> OK.
>
>
>  Have you looked at the source since commit f500721913f6728fc85d "Complete
>> Edge Weight Map Parameterization"?  With that checkin I tried to render all
>> type definitions in terms of graph_traits<> and property_traits<>.
>>
>
> Part of me says that it might be better to put your code in a namespace and
> then use the actual (internal) names of edge_descriptor, etc. to make the
> code shorter.  You can also, once you have a namespace, just make typedefs
> for "edge_descriptor" and such directly within the namespace so you can
> refer to them unqualified.  It's up to you whether you want to change that.
>
>
>  I'll look at iterator_facade.
>>
>> I'll combine implicit.cpp and implicit.hpp into just implicit.hpp.  All
>> the valid expression functions should be inline anyway.  I think having a
>> separate main.cpp makes things more readable.
>>
>
> It looks like you have done these in the latest checkin.
>
> I would recommend having your source(), target(), etc. functions take the
> graph by const reference; although it doesn't matter to your code since your
> graph type is small, I think it would be a better model for other users
> (with larger graph types) that you not copy graphs around unnecessarily.
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>