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-10 16:48:32

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

Apparently, me :)

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

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

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

> 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
andrew.n.sutton_at_[hidden]