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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-04-03 10:54:13

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

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_at_[hidden]>
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)
_______________________________________________