How do I "specialize boost::property_map directly"? This might be the key to the problem. My current shot in the dark is to try: template<> struct boost::property_map<ImplicitRingGraph, boost::edge_weight_t> { typedef EdgeWeightMap type; typedef EdgeWeightMap const_type; }; which gives me the error implicit.hpp:116: error: specialization of ‘template<class Graph, class Property> struct boost::property_map’ in different namespace /opt/local/include/boost/graph/properties.hpp:244: error: from definition of ‘template<class Graph, class Property> struct boost::property_map’ On Thu, Jun 24, 2010 at 5:22 PM, W.P. McNeill <billmcn@gmail.com> wrote:

Thanks for your help. Getting a little closer.

Once I get the edge properties working I'll look at traversal concepts other than AdjacencyGraphs. So far this has been the easy part for me.

I have been looking at the grid graph, but I couldn't figure out how to add weights to the edges of a grid graph. I can't find a simple example of an implicit graph with properties. (Which is why I'm trying to write one now.)

What do you mean by "Write an empty struct that inherits from all of the ones that you are going to model"? I didn't think there were concept base classes to inherit from.

Changing the property typedef in the implicit graph struct to

typedef boost::property<boost::edge_weight_t, float> edge_property_type;

making the get() functions take constant graph object references, and checking against the ReadablePropertyGraphConcept improves the compilation. I now no longer have pages of errors, which makes me think I'm on the right track.

I still have two errors, both of which I'm confused about.

1. graph_concepts.hpp:390: error: conversion from ‘EdgeWeightMap’ to non-scalar type ‘boost::typed_identity_property_map<size_t>’ requested

This is the same as before. This error makes me feel like I've got the wrong return value for one of my get() functions, but after double-checking they look right.

2. property_map.hpp:318: error: no match for ‘operator[]’ in ‘(const boost::typed_identity_property_map<size_t>&)((const boost::typed_identity_property_map<size_t>*)(& pa))[k]’

I didn't think any concept required operator[], so I'm not sure why this is happening. Line 318 is inside the inline get() function of the put_get_helper(), but I'm not using put_get_helper() in my code.

On Thu, Jun 24, 2010 at 1:25 PM, W.P. McNeill <billmcn@gmail.com> wrote:

...

I am writing a stripped-down implicit graph that I hope can be a useful template for others working with the Boost Graph library. The project is hosted at github. Excerpts from the source are in this email, and the full source is viewable online at http://github.com/wpm/Boost-Implicit-Graph-Example.

I am currently getting errors from the concept checking code which I don't understand and am looking for suggestions as to what I am doing wrong.

This is graph class.

struct ImplicitRingGraph { ImplicitRingGraph(size_t n):n(n) {};

// Graph concept typedef size_t vertex_descriptor; typedef boost::undirected_tag directed_category; typedef boost::disallow_parallel_edge_tag edge_parallel_category; typedef boost::adjacency_graph_tag traversal_category;

// AdjacencyGraph concept typedef RingAdjacencyIterator adjacency_iterator;

// PropertyGraph concept typedef boost::edge_weight_t edge_property_type;

// Additional types required by the concept-checking code. typedef std::pair<vertex_descriptor, vertex_descriptor> edge_descriptor; typedef size_t vertices_size_type; typedef size_t edges_size_type; typedef size_t degree_size_type; typedef void out_edge_iterator; typedef void in_edge_iterator; typedef void vertex_iterator; typedef void edge_iterator;

// The number of vertices in the graph. size_t n; }; typedef boost::graph_traits<ImplicitRingGraph>::edge_descriptor Edge;

I want the edges to have weights, so it models the PropertyGraph concept. The following functions implement the valid expressions.

EdgeWeightMap get(boost::edge_weight_t, ImplicitRingGraph& g) { return EdgeWeightMap(); }

EdgeWeight get(boost::edge_weight_t tag, ImplicitRingGraph& g, Edge e) { return get(tag, g)[e]; }

(Definitions of Edge, EdgeWeight, and EdgeWeightMap are visible online. I also define an adjacency iterator that is not shown here.)

I can write code that reads an edge weight.

ImplicitRingGraph g(5); EdgeWeightMap m = get(boost::edge_weight, g); boost::graph_traits<ImplicitRingGraph>::edge_descriptor e(0, 1); EdgeWeight w = get(boost::edge_weight, g, e);

However I get errors when I try to use the concept checking code.

function_requires< PropertyGraphConcept<ImplicitRingGraph, Edge, edge_weight_t>

...

();

The full error printout is huge, but there appear to be three relevant problems.

1. graph_concepts.hpp:406: error: conversion from ‘EdgeWeightMap’ to non-scalar type ‘boost::typed_identity_property_map<size_t>’ requested

The line in graph_concepts.hpp is

Map pmap = get(Property(), g);

inside the concept check for PropertyGraph. It looks to me like I have a function to handle this. I don't understand where boost::typed_identity_property_map<size_t> is coming from.

2. graph_concepts.hpp:408: error: no matching function for call to ‘put(boost::edge_weight_t, ImplicitRingGraph&, Edge&, size_t&)’

I didn't write any put() functions so I understand why I'm getting this. However, I would like the edge weights to be readable but not writeable (myEdgeWeightMap models a ReadablePropertyMap), and I can't figure out how to specify the read-only property in the graph defintion.

3. graph_concepts.hpp:390: error: no matching function for call to ‘get(boost::edge_weight_t, const ImplicitRingGraph&)’ graph_concepts.hpp:391: error: no matching function for call to ‘get(boost::edge_weight_t, const ImplicitRingGraph&, Edge&)’

Should I create functions identical to what I've already written, except with constant modifiers in front of the graph type? That feels like redundant source.

Thanks for any help you can give. Hopefully, a completed version of this example would be a useful resource for other BGL developers.

Thanks. I figured out how that I needed to put a boost namespace around the whole specialization sometime last night, and after I did everything built correctly. The mysterious non-scalar conversion error went away. Ultimately I think the source of my confusion lay in the fact that property graph concept types are defined in property_map structures while all other graph concept types are defined in graph traits. I was so in the habit of adding typedefs inside my graph class I overlooked the fact that property graphs do something else. In retrospect this is all clearly spelled out in the documentation, but if I was confused about it someone else probably will be too. Hopefully my sample at http://github.com/wpm/Boost-Implicit-Graph-Example can prevent someone from going down the same path. Thanks again for your help. On Fri, Jun 25, 2010 at 6:55 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Thu, 24 Jun 2010, W.P. McNeill wrote:

How do I "specialize boost::property_map directly"? This might be the key

...

to the problem.

My current shot in the dark is to try: template<> struct boost::property_map<ImplicitRingGraph, boost::edge_weight_t> { typedef EdgeWeightMap type; typedef EdgeWeightMap const_type; };

which gives me the error

implicit.hpp:116: error: specialization of ‘template<class Graph, class Property> struct boost::property_map’ in different namespace /opt/local/include/boost/graph/properties.hpp:244: error: from definition of ‘template<class Graph, class Property> struct boost::property_map’

You need to do:

namespace boost { template <> struct property_map<ImplicitRingGraph, boost::edge_weight_t> { ... }; }

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I'd be happy to include this in the examples directory. Just point me to the appropriate license boilerplate. I used forward_iterator_helper because that's what the Knight's Tour example in the Boost Graph Library book uses. If you can see any other implementation or stylistic issues, let me know. I'd like to make this a good example. On Fri, Jun 25, 2010 at 8:30 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Fri, 25 Jun 2010, W.P. McNeill wrote:

Thanks. I figured out how that I needed to put a boost namespace around

...

the whole specialization sometime last night, and after I did everything built correctly. The mysterious non-scalar conversion error went away. Ultimately I think the source of my confusion lay in the fact that property graph concept types are defined in property_map structures while all other graph concept types are defined in graph traits. I was so in the habit of adding typedefs inside my graph class I overlooked the fact that property graphs do something else.

In retrospect this is all clearly spelled out in the documentation, but if I was confused about it someone else probably will be too. Hopefully my sample at http://github.com/wpm/Boost-Implicit-Graph-Example can prevent someone from going down the same path.

Would it be worthwhile to put your example (or a variant of it) into BGL's example directory? To do that, you would need to license it under the Boost license, and I might change the formatting and/or naming conventions to fit BGL ones. Also, why are you using forward_iterator_helper rather than iterator_facade?

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I'll add the Boost license. I can change the capitalization convention. It's just aesthetics to me, and it makes sense in this context to be consistent with the rest of Boost. I have tabs in my source code. It looks like Github's source has a tabs-to-spaces conversion that's different than my editor and makes some lines look weird. I can change this easily enough. Is there a style guide for Boost and/or the BGL? (Quick Googling didn't turn up anything.) Is there a particular reason to use iterator_facade rather than forward_iterator_helper? On Fri, Jun 25, 2010 at 1:53 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Fri, 25 Jun 2010, W.P. McNeill wrote:

I'd be happy to include this in the examples directory. Just point me to

...

the appropriate license boilerplate. I used forward_iterator_helper because that's what the Knight's Tour example in the Boost Graph Library book uses. If you can see any other implementation or stylistic issues, let me know. I'd like to make this a good example.

License information is at <URL:http://www.boost.org/users/license.html>. The one thing I didn't like about the code is that it uses a different capitalization convention than Boost; Boost normally uses the STL convention of lowercase words separated by underscores. I don't know if this is a GitHub issue, but it looked like the indentation of your code was inconsistent. Remember that tabs are forbidden in Boost, too (I don't know if your code has them). If you post a new version of the code, I'll look through it again.

-- Jeremiah Willcock

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On Fri, 25 Jun 2010, W.P. McNeill wrote:

I've made the changes you suggested, including modeling IncidenceGraph instead of AdjacencyGraph.  Let me know if this looks good for the Boost examples.

You might want to model VertexListGraph as well, as well as having a vertex_index property map (many algorithms want that). You can probably use identity_property_map (or actually typed_identity_property_map<size_t>) as the vertex_index map type, so you don't need to write too much code for that. Some relevant code is near the bottom of <boost/graph/compressed_sparse_row_graph.hpp>; look for the parts that define property_map<> and get() for vertex_index_t. Note that you can model AdjacencyGraph in addition to IncidenceGraph; they do not conflict. You can use the code in <boost/graph/adjacency_iterator.hpp> to create the AdjacencyGraph model for you without needing to make any new iterator types. Did you try any algorithms on your graph type (and property maps)? That would be a good way to check whether everything is provided that needs to be. BFS or Dijkstra's algorithm would be good places to start; note that both of those need VertexListGraph and also need a vertex_index map by default. Trying to write your graph to a Graphviz file would also be a good test, especially since you have such a figure in your documentation anyway. Your code seems to be inconsistent on whether to use the internal names of various types (such as the actual definition of vertex_descriptor) or refer to them using graph_traits. I would still prefer that you use iterator_facade (from Boost.Iterator) instead of forward_iterator_helper; I'm not sure forward_iterator_helper is even officially documented as part of Boost anymore. Your code should get a lot simpler using iterator_facade anyway. Would it be possible for your whole example to be in the .cpp file (or alternatively, only in the .hpp file)? I think having all of the function bodies present where they are declared will make the code easier to read, and the program is not large enough where that will get unreadably long. You could have your graph type in one .hpp file and main() in a .cpp file if you want, or pack everything into the main .cpp file (maybe with a line indicating where the graph type itself is vs. the code that uses it). I think that this code will be worthwhile to have as a BGL example once it is all finished. There are relatively few (basically no) simple examples of creating a graph type from scratch, and the standard graph types in BGL are very complicated (both to be flexible with user-defined properties and to be compatible with obsolete compilers). I am grateful for the time you're spending putting this together. To respond to your other email, I don't think there is a Boost style guide, but you can look at <URL:https://svn.boost.org/trac/boost/wiki/Guidelines/Requirements> and the pages that links to for lots of information. You don't need to worry about file naming conventions and such since I will rename your files when putting them into Boost anyway. The BGL style guide is basically just to model your code after the files that are there already (i.e., I don't think the rules are written down explicitly in a place that's easy to find); I think the style is basically K&R indentation but that isn't enforced. New code added to BGL generally keeps whichever style its author wants, other than things like tabs and naming conventions that are Boost-wide. -- Jeremiah Willcock

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

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@gmail.com> 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@osl.iu.edu>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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

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@osl.iu.edu>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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

The forward declarations are tricky because ring_adjacency_iterator_generator adapts ring_incident_edge_iterator, which in turn has template parameters defined in terms of graph_traits<>. After playing around a bit more I was able to use boost::adjacency_iterator_generator::type by making it a base class of ring_adjacency_iterator_generator. This ends up only saving a few keystrokes from the version that derives it directly from boost::adjacency_iterator, but it still feels like the right thing to do. I was also able to keep everything parameterized through graph_traits<>. This example feels done. Thanks for your help. On Wed, Jun 30, 2010 at 9:50 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Tue, 29 Jun 2010, W.P. McNeill wrote:

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.

You have the actual types that vertex_descriptor, etc. are defined to, right? Can you use those as the arguments to adjacency_iterator_generator?

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users