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

Subject: Re: [Boost-users] [BGL] vertex_index_t,edge_index_t?
From: Geoff Hilton (geoff.hilton_at_[hidden])
Date: 2008-12-10 14:09:37

Andrew Sutton wrote:
> 
>     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 cours e
>     (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.

Great! I'm happy to know I was right! The BGL does indeed take some 
getting used to.

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

Who do we have to bug to get improvements in the documentation and 
examples? :)

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

Out of curiosity (keeping in mind I'm still wrapping my head around 
graph theory), algorithmically speaking; why would I need to provide an 
index map if iterating over vertices and in/out edges with iterators is 
good enough? Is it a question of base algorithm or of implementation 
optimizations (switching out iterators and distances with 
container-specific pointer or index arithmetic as an oversimplified 
example)?

> Maintaining the 
> indices can save you a significant amount of time if you have to keep 
> creating new maps (and aren't removing vertices).

How so? Could you provide a brief example? I ask because iteration 
doesn't seem to require explicit index maps to be defined (with the 
default set of provided container selectors at any rate). Even then when 
I had the index maps defined explicitly they were never modified (all 
were always zero) but everything functioned normally anyway, so any code 
that uses index maps (that I've seen thus far) seems to use them for 
their side effects (ie. the fact that they point to or are contained by 
somewhere specific), not for their contained value.

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

Awesome! I'll definitely be checking that out, is the plan for it to 
eventually replace the current BGL implementation?

Also, I recently came across the PBGL project; I haven't tested it, but 
is it not ready for use in a commercial application yet? My code will 
definitely need to be parallelized.

Thanks,
Geoff