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-15 11:55:39

Andrew Sutton wrote:
> 
>     Who do we have to bug to get improvements in the documentation and
>     examples? :)
> 
> 
> Apparently, me :)

Consider yourself bugged! :D

>  
> 
>     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)?
> 
> 
> It's all about labeling and efficiency. Most graph algorithms (e.g., 
> from the Cormen book) associate various data with vertices and edges - 
> like edge weight or flow/capacity, vertex color, etc. If your vertex or 
> edge type does not explicitly declare member variables that can be used 
> to satisfy these requirements, then you have to create an "exterior" 
> label or property. The most efficient way to access this information is 
> using a vector, and the only way to get data out of a vector is to use 
> an index. And to get the index, you need a vertex index map.
> 
> Long story short, most algorithms in the BGL create exterior labels as 
> vectors, hence requiring index maps. An alternative, and infrequently 
> explored option is to create the exterior labels as unordered_maps, 
> mapping descriptors to their label values.
> 
> Both 2007 and 2008 SoC projects address this issue in basically the same 
> way.
>  

Ahhh, okay.

> 
> 
> 
>         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? 
> 
> 
> Iteration is just traversal. Labels (properties) require a form of 
> associativity (edge descriptor to weight, for example).

That would indeed differentiate them!

>  
> 
>     Awesome! I'll definitely be checking that out, is the plan for it to
>     eventually replace the current BGL implementation?
> 
> 
> Hard to say. There aren't very many 20K+ LOC libraries submitted to 
> Boost (I'm just projecting the size based on the current version). I 
> would hope that my work does replace the BGL, but that's something to be 
> addressed in the future. I'm also trying to target C++0x as the 
> implementation language, including concepts so it won't even be 
> generally compilable for quite some time (accounting for compiler bugs too).
> 
> This version is easily a couple years away from practical use.
>  

Dang.

> 
>     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.
> 
> 
> That's something you'd have to ask of the authors. I want to say "more 
> or less", but I couldn't certainly be wrong.
> 
> I was also trying to build my version in a way that would make it easy 
> to port PBGL to the new interfaces, but I have no idea if that will work 
> or not. I'm thinking that better parallelization and distriibution 
> support will appear in various Boost libraries in the near future, and 
> that support will creep into the graph library.
> Andrew Sutton

It'd definitely be nice if parallelization and distribution support were 
made more prominent because considering current technological trends and 
the market, the only reasonable way for applications to improve in 
performance (beyond initial development) is by being multi-threaded. 
Case in point: the Visual Studio 2008 IDE like 2005, still hasn't been 
made multi-threaded - only the compilers are.

Anyway thanks for your attention, I look forward to the changes in the 
documentation!

Geoff