Re: [boost] Re: VertexListGraph (Was: a small bug in BGL doc)

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-02-05 23:54:43

For the graph_traits problem, I've considered several unsatisfactory
solutions in the past... however your email got me thinking of another
possibility.

Something I've been meaning to do is add a traversal_category type to the
graph_traits that mirrors the graph concept hierarchy. If I did this, it
would also be possible to change graph_traits in the following way:

  template <typename G>
  struct graph_traits
    : public G::traversal_category::template bind<G>
  { };

So I'd have the tag class do double duty. They would also
extract the appropriate associated types.

  struct graph_tag {
    template <typename G>
    struct bind {
      typedef typename G::vertex_descriptor      vertex_descriptor;
      typedef typename G::directed_category      directed_category;
      typedef typename G::edge_parallel_category edge_parallel_category;
    };
  };
  struct incidence_graph_tag : public graph_tag {
    template <typename G>
    struct bind : public graph_tag::template bind<G> {
      typedef typename G::edge_descriptor        edge_descriptor;
      typedef typename G::out_edge_iterator      out_edge_iterator;
      typedef typename G::degree_size_type       degree_size_type;
    };
  };

Aside: it might be good to have a mutability_category as well, and move
the edge_parallel_category into there since it does not have anything to
do with graph traversal.

I'd be interested to here opinions on this from BGL users.

Cheers,
Jeremy

On Tue, 6 Feb 2001 hankel_o_fung_at_[hidden] wrote:

hankel> --- In boost_at_y..., Jeremy Siek <jsiek_at_l...> wrote:
hankel> [snip]
hankel> > The AdjacencyGraph concept is a bit odd, it is somewhat frivolous 
hankel> since
hankel> > IncidenceGraph really covers the same functionality (and more).
hankel> > AdjacencyGraph is there just because I can imagine situations where
hankel> > adjacent_vertices() would be more convenient to use than out_edges
hankel> (). One
hankel> > thing in favor of keeping AdjacencyGraph is that it is trivial to
hankel> > implement using the graph/detail/adjacency_iterator class. I should
hankel> > document this class and make it public.
hankel> > 
hankel> You are right. Thanks for telling me about this class.
hankel> 
hankel> [snip]
hankel> > Also, the algorithms in BGL that require vertex traversal
hankel> > also require out-edge traversal, so it is convenient to group them
hankel> > together.
hankel> Hmmm, but the problem is, there are algorithms that require
hankel> traversal across all vertices and out-edge traversal but not
hankel> adjacent-vertex traversal. So one may have to define something
hankel> they don't need when using a BGL algorithm. A similar situation
hankel> occurs when one doesn't want to specialize the graph traits in
hankel> constructing a new graph class. For example, to construct a graph
hankel> class that models the VertexListGraph concept, one should at least
hankel> typedef in_edge_iterator as void. Although this is technically
hankel> simple and acceptable, it is still a penalty --- especially to
hankel> the uninitiated (like me).
hankel> 
hankel> Cheers,
hankel> Hankel
hankel> 
hankel> 
hankel> 
hankel> 
hankel> 

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------