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 20:43:17

I was able to implement an adjacency_iterator by writing my own
iterator_adaptor of the out_edge_iterator, but it would be better to get the
class defined in the Boost library working.

On Mon, Jun 28, 2010 at 4:15 PM, W.P. McNeill <billmcn_at_[hidden]> wrote:

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