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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-04-05 04:11:13

Hi Johnny,

>> 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.

That's right.

>> 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?

For the purpose of adding an edge between two vertices, for example.
 
>>Is it possible to
>> insert two 'City' objects which are equal?
> 
> I think that should probably depend on the underlying
> graph type.

Eh, if you add two equal City instances, then how you distinguish them
later. Say you want to find all roads from a given city, say "Moscow". You
have two cities by this name so you really have to either:
1. Require that 'City' instances have some other attribute, which makes them
unique.
2. Maintain that unique key outside of 'City' instance.

>> 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.

FWIW, it would require all types used as vertices to have both operator==
and hash function. It would also require you to use hash table, which is
not part of C++ standard or Boost yet.

I really not sure if using user types to identify vertices makes sense or
not. User types makes the model a bit simpler. But for example, 
my use case is graph with 'class Instruction' as the type I want to store in
vertices. For now, I'm just storing vector<Instruction> separately from the
graph. It would be nice to make Instruction the type of vertex, but I don't
know even how to implement operator== for that type :-(

And of course, I don't want any graph algorithm to store vector<Instruction>
anywhere.
  
>> 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?

So, you'd still have to use property map to obtain user-interesting
information about an edge?

>> 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?

Probably:

   for (tie(i, e) = vertices(g); i != e; ++i) {
        City& c = get(vertex_data, g, *i);
   }

vs.

   for(tie(i, e) = vertices(g); i != e; ++i) {
        City& c = *i;
   }

>>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.

Yea, it would be really nice to think for graph as vector<City> with some
additional information about edges. If only we knew how to identify
vertices in an efficient way.

I can think of those approaches:

1. The 'vertex_descriptor' is retired. If you want to idenitify the vertex,
you use vertex iterator. The same vertex iterator is used to index property
maps. The drawback is that iterator should be stable, and so might take
more space than vertex_descriptor. 

2. Use several way to identify a vertex. E.g. if you want to add read
between two cities, you'd use City instances. If you want to be really
fast, you use vertex_descriptor. This requires that the way City instances
are looked up is customizable (e.g. set vs. hashset).
Whether default vertex_iterator iterates over City& or vertex_descriptor is
a separate question -- in either case one should be able to iterate over
both.

- Volodya