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

From: Johnny Yune (prosonance_at_[hidden])
Date: 2004-04-02 19:59:40

"Vladimir Prus" <ghost_at_[hidden]> 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/