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-29 10:08:03

On Mon, 28 Jun 2010, W.P. McNeill 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.)

It is used indirectly (though lookup_edge()) but that function will fall 
back to using out_edges() if it can't find edge().  It just improves the 
complexity of the algorithm if you have a version of edge() that is faster 
than searching the list returned by out_edges().

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

I have a suspicion that adjacency_iterator is trying to instantiate 
graph_traits<graph>, which isn't complete yet since you're still giving 
its definition (i.e., you're trying to use a class to define itself).  If 
you use "typedef void adjacency_iterator;", can you instantiate 
adjacency_iterator for your graph later (outside graph_traits)?

-- Jeremiah Willcock