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?
What should I specify for the traversal_category if I model all of them with a single object?

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'll add Dijkstra's algorithm to the main() function.

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

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.

On Fri, Jun 25, 2010 at 7:41 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
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
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users