Re: [Boost-users] [BGL] vertex_index_t,edge_index_t?

Subject: Re: [Boost-users] [BGL] vertex_index_t,edge_index_t?
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2008-12-08 19:33:38

>
> Aha! I had a feeling it was being wasted (in my code). Indeed it doesn't
> automatically assign indices (neither mine nor that of the BGL), it always
> remains zero throughout execution, this seems like a rather massive waste of
> memory to me. Since many BGL algorithms use the index properties I do
> believe they and their relationship with container selectors (since you say
> they also provide default index properties) merit some in depth explanation
> in the documentation as there currently is none whatsoever aside from their
> brief mention of existence and a paragraph on "what selector to choose to
> use the desired container".
>
> Aside from being indices of some sort I had no real idea of how to best
> (appropriately) use them since they were taking up memory, I ended up
> conceding them as a necessary evil/requirement of BGL algorithms despite not
> touching them in my own code except near algorithm calls (I'm still trying
> to wrap my head around graph theory).
>
> I think you're right about the issue only being half solved, do you know if
> there's a better way of solving the issue? Might there be a better (read:
> less dependency-inducing) way to provide default arguments, or do the index
> properties exist to supply the defaults? Failing that (and this is only
> theoretical in my current case since I can use defaults because of vecS) how
> might I use the index property in a more productive/less wasteful manner?
> [*]Don't properties already have an index by virtue of belonging to vertices
> and edges which are stored in containers? What about creating a property
> that explicitly exists only to provide default arguments (and is documented
> as such along with their relation to container selectors)? This property
> could also have a default state of course (which would be necessary anyway
> to remain compatible with older code).
>
> I hope the above didn't sound like I was bashing the documentation or
> whatnot, I am overall very grateful to have it. :)
>
> [*] Heh, after rereading this bit I think I answered that question myself.
> The BGL needs to know how to access the selected container in its'
> implementation as much as we need to access it through its' interface, thus
> the index property isn't necessarily always an int, it might be a Node*
> (with listS for example) right?
>
> Please feel free to confirm/correct me if and wherever I'm right/wrong.
> Thanks for the quick reply Andrew!
>

In a word, "yes". To all of it :) It takes a good month or so of work with
the BGL to really understand property maps, interior properties, exterior
properties, and bundled properties, and then another month on top of that to
understand the intricacies of their interaction with different
instantiations of graph classes.

I'm not sure if the documentation contains a statement like, "A property map
abstracts the ability to read and write data associated with an edge or
vertex", but it probably should. The use of the _t types is just a mechanism
of "naming" a property map with a type - and of course getting that property
map off of the graph. The documentation is not entirely forthcoming about
all of this. And since *every* example in the distro uses vecS, vecS, its
hard to tell how things work.

The memory isn't really being wasted if you're using it. In most cases,
you're going to have to provide an index map anyways. Maintaining the
indices can save you a significant amount of time if you have to keep
creating new maps (and aren't removing vertices).

You might want to look here:
http://svn.boost.org/svn/boost/sandbox/SOC/2007/graphs. It has some
abstactions that make properties a little easier to work with. It also has
an undirected_ and directed_graph adjacency list implementations that only
work with bundled properties, and hide some of the weirdness of using vecS,
listS, etc.

If you're really feeling bold, you can look at the 2008 version - which I'm
still semi-actively working on - that will essentially be a complete
re-implementation.

Andrew Sutton
andrew.n.sutton_at_[hidden]