Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net