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-29 13:26:40

It looks like the adjacency_iterator created by adjacency_iterator_generator
was being defined in terms of  vertex_descriptor and out_edge_iterator,
which are in turn defined via graph_traits<>, which would cause this
problem.

I got a little closer to an ideal solution by putting

    typedef ring_adjacency_iterator adjacency_iterator;

in the graph class and forward-defining ring_adjacency_iterator, then later
on in implicit.hpp deriving ring_adjacency_iterator
from boost::adjacency_iterator like so

  class ring_adjacency_iterator:public boost::adjacency_iterator<
    graph,
    vertex_descriptor,
    out_edge_iterator,
    boost::use_default> {
  public:
    typedef boost::adjacency_iterator<
      graph,
      vertex_descriptor,
      out_edge_iterator,
      boost::use_default> parent_class;
    ring_adjacency_iterator() {};
    ring_adjacency_iterator(const out_edge_iterator& ei, const graph* g):
      parent_class(ei, g) {};
  };

I didn't have to typedef the adjacency_iterator to void in the graph
definition, so this is a valid AdjacencyGraph model.

I like this better than writing my own iterator_adaptor because it
uses boost::adjacency_iterator, though it feels a little hacky because the
body of ring_adjacency_iterator is mostly cut-and-pasted
from adjacency_iterator.hpp.

I'd like to find a way to define the adjacency iterator with the generator
using the statement

  boost::adjacency_iterator_generator<graph, vertex_descriptor,
out_edge_iterator>::type

but I haven't been able to do it.  This generator statement relies on
graph_traits<> properties vertex_descriptor and out_edge_iterator, so has to
come after the definition of implicit_ring::graph.  But that means I have to
have a forward declaration of the adjacency_iterator, and I don't know how
to forward-declare something I'm getting from
 boost::adjacency_iterator_generator<>::type.

It's still pretty good, but if this is going to be example code I'd like to
make sure I'm doing it the best way possible.

On Tue, Jun 29, 2010 at 7:08 AM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> 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 mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>