Re: Re: [BGL] forced client complexity
"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/
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
participants (6)
-
Johnny Yune -
Vladimir Prus