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.
(btw, if possible, it would be nice to know your real name, so that I could
write "Hi <your real name>")
> 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
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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk