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-26 00:35:10

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