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