From: Johnny Yune (prosonance_at_[hidden])
Date: 2004-04-02 19:59:40
"Vladimir Prus" <ghost_at_[hidden]> wrote:
> (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
> 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
> > member of the node-type's class?
> I don't think "index" should be type of 'City'
Nor does it seem a logical candidate for a member. In
fact, as a client, you shouldnt and neednt know
anything about it.
> > If, instead, it is a
> > synthesized construct for communication between a
> > graph and the algorithm operating over it, why
> > the client be responsible for its maintenance
> > of the framework? What are the advantages of this
> > approach? What are the disadvantages of
> > 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 youre looking at this from the
framework side instead of the client side. Thats
fine, but it still isnt clear to me why adding
another layer of abstraction should affect the
internal workings so heavily. Ill try to address
your questions with respect to how I would probably do
>how do you identify vertices? If you use
> "City&" you'd have some problems:
> 1. How vertices are really identified? Using
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
> If not, how to insure uniqueness?
I guess you would want to make sure to not insert
> Do we really want 0(log n) lookup on each
Huh? I admit to not being intimate with BGLs
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
> 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 shouldnt 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.
Youll 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
Iterating over cities sounds absolutely reasonable to
me. Much more so than iterating over some arbitrary
> 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
Do you Yahoo!?
Yahoo! Small Business $15K Web Design Giveaway
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk