Re: [boost] Re: Re: [BGL] forced client complexity

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-04-02 07:35:14

Provisional Dissonance wrote:
> >Yea, but first the original poster should indicate if
>
> this is what he's
>
> >looking for -- I never needed this myself.

Hi,
(btw, if possible, it would be nice to know your real name, so that I could 
write "Hi <your real name>")

> At
> a basic conceptual level, I think of a graph as a data
> structure composed of nodes and edges.  If I'm
> modeling a family tree, I expect the nodes to be
> objects of some family-member class.  C++ exposes many
> robust and elegant methods for modeling the
> family-member - why should I, as a client, have to use
> property-maps at all?  

Hmm, interesting question. In fact, something like

   typedef graph<City, Road> Road_map;

looks quite reasonable to me.

> If the node's "index" is
> related to the object, why would it not be a natural
> member of the node-type's class?  

I don't think "index" should be type of 'City' class.

> If, instead, it is a
> synthesized construct for communication between a
> graph and the algorithm operating over it, why should
> the client be responsible for its maintenance instead
> of the framework?  What are the advantages of this
> approach?  What are the disadvantages of simplifying
> things for the client?  This is the type of design
> issue that I intended to question with my initial
> post.

I think the biggest problem is: how do you identify vertices? If you use 
"City&" you'd have some problems:

1. How vertices are really identified? Using operator==? Is it possible to 
insert two 'City' objects which are equal? If not, how to insure uniqueness?
Do we really want 0(log n) lookup on each 'add_vertex'.

2. Even if 'City' objects in a graph are unique, how will add_edge be 
implemented? Do you need O(log n) lookup to find internal adjacency lists?

3. What's edge, and how it is identified? For example, 'Road' might not 
contain source/target vertices, but still we need to be able to find 
source/target vertices. 

One possible solution that I see is the make vertex_descriptor be always 
pointer type. It will point at some internal structure but also provide 
operator* which will return 'City'. Or, maybe, it should be possible to 
iterate over values of 'City', not only over values of vertex_descriptor.

I still don't know if using City to identifiy vertices is feasible.

- Volodya