Boost logo

Boost :

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>")

> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at