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

From: hankel_o_fung_at_[hidden]
Date: 2001-02-12 07:59:52

It's been quite a few days since I last checked out this discussion
group. It's amazing to see the number of postings growing so quickly.
(There were almost no postings during the first few months ...)

--- In boost_at_y..., Jeremy Siek <jsiek_at_l...> wrote:
> 
> 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.
I am not professional enough to judge if this is really a good idea,
but I am alarmed by the phrase DOUBLE DUTY. Are you sure you won't
have to decouple the two duties in the future?

> 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;
>     };
>   };
This looks interesting, but I'm afraid of losing flexibility.
Defining an incidence_graph_tag makes IncidenceGraph seem more like
an implementation than merely a concept. But as I said, I am not a
professional programmer.

> 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.
Uhhh, perhaps it has something to do with edge traversal??? I don't
know. In the field (textile/clothing) I work in, I seldom deal with
such monsters as multiple edges. The monsters I used to cater are
coexisting but interacting edges of multiple *types* (namely, 
forward/backward/bidirectional arcs --- yes, we have directed and
undirected arcs in the same graph, and both forward and backward
arcs from a node are out arcs).
  
> I'd be interested to here opinions on this from BGL users.
I am happy to learn from the Boost guru's.

Cheers,
Hankel