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-25 22:41:32

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