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-08 17:59:00

Andrew Sutton wrote:
> 
> 
> On Mon, Dec 8, 2008 at 2:41 PM, Tim Keitt <tkeitt_at_[hidden] 
> <mailto:tkeitt_at_[hidden]>> wrote:
> 
>     Geoff Hilton <geoff.hilton <at> t-optlogic.com
>     <http://t-optlogic.com>> writes:
>      > Where:
>      > typedef boost::property<
>      >              boost::vertex_index_t,
>      >              unsigned long long,
>      >              MyVertexProperty>            
>     VertexPropertyWrapper_type;
> 
>     I believe adjacency_list has an internal vertex index property by
>     default when
>     choosing vecS for the vertex container, so you should not need to
>     add it. Do
>     things fail without it there?

Great question Tim, I tried removing the wrapper typedefs and replacing 
them directly with the My*Property typedefs and it did indeed compile 
without error. Theoretically, what would the effect be were I to use a 
custom container or listS though instead? Would I need to explicitly 
provide index properties?

Thanks for your reply Tim!
> 
> That's correct.
> 
> Just declaring a vertex index as a property (either bundled or interior, 
> as here) won't buy you any new functionality. It just provides a place 
> where you can assign an index for each vertex or edge. The problem that 
> this half-solves is that nearly every algorithm in the distro requires a 
> vertex index map (or edge index map, more rarely), and providing this 
> will allow the default arguments to automatically extract a property map 
> for vertices/edges.
> 
> It won't - or shouldn't??? automatically assign indices. Also, if you 
> remove a vertex or edge, you may have to renumber vertices.
>  
> Andrew Sutton
> andrew.n.sutton_at_[hidden] <mailto:andrew.n.sutton_at_[hidden]>

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!
Geoff