Re: Re: [BGL] forced client complexity
Jeremy Siek" <jsiek@osl.iu.edu> wrote in message news:
So I think your question can be boiled down to two questions, why does the BGL use vertex descriptors? and why does the BGL use property maps?
That probably restates my question more succinctly than I would be able to.
The BGL graph interface was designed so that many different graph data structures could be uniformly manipulated. It sounds like the data structure that you are most familiar with is where each node is an object, and the connecting structure of the graph is represented with pointers.
For my na�ve endeavors, I most often use adjacency matrices.
However, another important graph data structure is the adjacency list representation, where there are no node objects. Instead there is just an array of lists of integers. An integer n is associated with each node, and the out-edge list for a node is at offset n in the array.
The vertex_descriptor abstraction provides an opaque handle to a "vertex", whatever that may be for the data structure. For one graph type that may be node*, for another int. The purpose of the property map interface is to
That seems like an intuitive way for the back-end to work. Why should I, as a client, need to concern myself with those details, though? I�m sorry if I sound critical, but I just don�t understand. To me, it feels like using some sort of balanced tree container and having to concern myself with whether a node is red or black � why do I need to know? provide a
uniform way for an algorithm to access data that is associated with a node or edge. Again, there are many ways that such an association can be implemented, with various time, space, and convenience tradeoffs. Here are some examples:
1. Associated data is a member of a struct 2. Data is in an array, organized by vertex index offset 3. Data is in a hash table, somehow keyed on the vertex.
Now, the problem you're pointing out is that the extra level of indirection of the property map makes the syntax rather unwieldy for accessing data. For example, instead of:
v->color
one must write:
get(color_map, v)
Actually, what I really wanted clarification on was why the task of managing this mapping was left to the client instead of the underlying graph structure. The differences in syntax, above, are only indications of my confusion about the semantics. To wit, given your examples, I wouldn�t necessarily expect v->color to have anything to do with the color_map. v->color looks like a property of a vertex, while get(color_map, v) looks like a property of a graph.
(not to mention the trouble of setting up the
color_map > to begin with)
Well, this does make things a lot more complex. The need for such mappings is quite clear to me � the need for the client to �set them up� as opposed to the graph is unclear to me, though. If I were to ask an algorithm to generate a chromatic number over a graph, I could envision having a property map of some possible coloring returned to me. Why I would have to set one up or pass one in, though, I am unclear on. In reviewing my post, I am realizing just how astute you were to identify the property map as a major source of confusion for me � I am only beginning to be able to articulate why it �feels� unnatural for me. I guess the big question, then, is �why use property maps instead of functors?� Would not functors also allow communication between arbitrary user-defined vertex types, the graphs that store them (even if only by lookup mapping to some arbitrary internal data type), and the algorithms that operate over them? My gut tells me that it is so. It also seems like using functors would be a natural way to help preserve clarity � if an algorithm requires that every vertex have an index or a name or a color et cetera, mightn�t it be natural to pass in a functor that can extract, generate, or synthesize the required property? Such functors may also be good candidates for being defaulted, which could significantly help to simplify client code. Isn�t that, after all, the model that our beloved standard library follows with its generics? Thanks, again, for entertaining my questions. I am highly pleased to be soliciting rationale and intent instead of the rabid defensiveness or dismissal that I probably deserve. __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/
Hi Johnny, On Apr 2, 2004, at 8:01 PM, Johnny Yune wrote:
That seems like an intuitive way for the back-end to work. Why should I, as a client, need to concern myself with those details, though?
Because you need to choose which data structure has the right time/space efficiency tradeoffs for the problem you are trying to solve. (I could imagine a graph library that makes that decision for the user, however, I don't think the field of artificial intelligence has progress far enough to make that possible) Of course, after you've chosen which graph type you want, the BGL hides the implementation details from you. That's part of the job of the vertex_descriptor.
Actually, what I really wanted clarification on was why the task of managing this mapping was left to the client instead of the underlying graph structure.
I'm not really sure what you mean by "the task of managing". Could you clarify what that consists of? In the BGL, there are two kinds of property maps, internal and external. Internal properties are managed by the graph object, in the sense that the lifetime of the property objects is tied to the lifetime of the graph object. The client obtains the internal property map from the graph, using one of the get() functions. External properties are not managed by the graph object, but created by the client. Have you tried using internal properties, or only external? Perhaps the internal property maps would fulfill what you are looking for? BTW, it is possible to bypass using the property map when using adjacency_list. Here's the syntax: get(vertex_color_t(), g, v)
The differences in syntax, above, are only indications of my confusion about the semantics. To wit, given your examples, I wouldnt necessarily expect v->color to have anything to do with the color_map. v->color looks like a property of a vertex, while get(color_map, v) looks like a property of a graph.
Both access the property of a vertex.
(not to mention the trouble of setting up the
color_map > to begin with)
Well, this does make things a lot more complex. The need for such mappings is quite clear to me the need for the client to set them up as opposed to the graph is unclear to me, though. If I were to ask an algorithm to generate a chromatic number over a graph, I could envision having a property map of some possible coloring returned to me. Why I would have to set one up or pass one in, though, I am unclear on.
Yes, that would seem annoying. That is why the BGL provides defaults for the property map parameters in many of the algorithms. Usually they default to asking the graph object for an internal property map. So the client only needs to pass in the property map separately when the graph object does not provide it.
In reviewing my post, I am realizing just how astute you were to identify the property map as a major source of confusion for me I am only beginning to be able to articulate why it feels unnatural for me. I guess the big question, then, is why use property maps instead of functors?
I fail to see how functors could be used to solve this problem. Perhaps you could explain in more detail.
Thanks, again, for entertaining my questions. I am highly pleased to be soliciting rationale and intent instead of the rabid defensiveness or dismissal that I probably deserve.
You're welcome. Cheers, Jeremy _______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington Graduating in August 2004 and looking for work C++ Booster (http://www.boost.org) _______________________________________________
participants (2)
-
Jeremy Siek -
Johnny Yune