RE: [boost] [Review] Boost Graphs Library (GGCL)

From: jsiek_at_[hidden]
Date: 2000-08-30 16:18:18

Good question, because as you all know, void* should never be used
unless there is a *very* good reason.

The reason for void* is to enable the use of vertex_descriptor and
edge_descriptor in properties. In several of the GGCL examples, we
record the predecessor vertex during a graph search to encode the
search tree. In the examples we used an external property accessor for
the predecessors, but what if we had wanted to use an internal
property (a plugin)?

adjacency_list<vecS, vecS, directedS, 
               plugin<predecessor_tag, vertex_descriptor> >
                                       ^^^^^^^^^^^^^^^^^ 
But now we have a mutual recursion problem. We can't get the
vertex_descriptor type until we have the full adjacency_list type, and
we can't construct the adjacency_list type without first having the
vertex_descriptor type. I created the solution for this a few weeks ago,
which is to strip the EdgePlugin and VertexPlugin information from the
vertex_descriptor/edge_descriptor types (by making vertex_descriptor
either void* or size_t depending on the VertexList type) and adding a
new traits class (not yet documented):

template <class EdgeList, class VertexList, class Directed>
struct adjacency_list_traits {
  typedef ... vertex_descriptor;
  typedef .. edge_descriptor;
};

Cheers,

Jeremy

Gary Powell writes:
 > > The problem with this is that the value_type that will go into the
 > > container is
 > > really an implementation detail that the user shouldn't have to know
 > > about.
 > > 
 > Ok, that brings up the question, "Why are you using void *, as the value
 > type?"
 > 
 >   Inquiring minds wish to know...
 >   -gary-
 > 
 > 
 > 
 > 
 > 
 >