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