"Vladimir Prus" <ghost@cs.msu.su> wrote:
Hi, (btw, if possible, it would be nice to know your real name, so that I could write "Hi <your real name>")
Ah, excuse me. It would please me for you to call me Johnny Yune. <snip>
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.
Nor does it seem a logical candidate for a member. In fact, as a client, you shouldn�t and needn�t know anything about it.
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:
It seems like you�re looking at this from the framework side instead of the client side. That�s fine, but it still isn�t clear to me why adding another layer of abstraction should affect the internal workings so heavily. I�ll try to address your questions with respect to how I would probably do it, though.
how do you identify vertices? If you use "City&" you'd have some problems:
1. How vertices are really identified? Using operator==?
Really identified by whom and for what purpose?
Is it possible to insert two 'City' objects which are equal?
I think that should probably depend on the underlying graph type.
If not, how to insure uniqueness?
I guess you would want to make sure to not insert duplicate vertices.
Do we really want 0(log n) lookup on each 'add_vertex'.
Huh? I admit to not being intimate with BGL�s internals, but it seems like a hashed set of Cities to indexes or whatever the underlying graph structure wants to use to identify nodes would be reasonable and speedy.
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?
Again, using a City as a node-type shouldn�t affect the runtime. If you can think of a way to define a vertex that allows o(1) lookup, I can probably give you a city->your_vertex_type hashmap that allows you to maintain that speed.
3. What's edge, and how it is identified?
I would leave that up to the underlying container. You�ll notice that in my original post, my scratchy pseudocode declared a graph as g<vertex_type, edge_context_type>. I kind of imagined edge_context as being some sort of arbitrary meta-data about the link, generally useful only to the client. Maybe the edge context could be a simple member of the graph-managed property map?
For example, 'Road' might not contain source/target vertices, but still we need to be able to find source/target vertices.
The whole point of the abstraction is to free the client from trying to figure out how to fit cities into roads. The underlying container could certainly keep a mapping from one to another.
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'.
Would that simplify things for the client?
Or, maybe, it should be possible to iterate over values of 'City', not only over values of >vertex_descriptor. Iterating over cities sounds absolutely reasonable to me. Much more so than iterating over some arbitrary vertex_descriptors, even.
I still don't know if using City to identifiy
vertices is feasible. I have no reason to think otherwise and I do think it sounds simpler from a client-side perspective. Food for thought. Thanks, prs __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/