[boost] [graph] A few additions to propose to BGL

Subject: [boost] [graph] A few additions to propose to BGL
From: Mikael Persson (mikael.s.persson_at_[hidden])
Date: 2013-05-19 17:20:53

Hi all,

I have developed a number of small additions to the BGL, nothing major,
just things that were useful to me and more practical as an extension to
BGL instead of as a separate library, and if you're interested, I'm willing
to contribute them back. These are non-intrusive additions, no
modifications of existing BGL code is required (although some can be
discussed, see below).

The proposed additions are:

1) Additional property-maps to fill the void between bundled properties and
boost::property_map<> mechanisms. Incl. descriptor-to-bundle maps,
bundle-to-property maps, composite maps (i.e., chaining property maps), etc.
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_alg/bgl_more_property_maps.hpp

2) A few more property-tags that are common for graph algorithms.
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_alg/bgl_more_property_tags.hpp

3) A few more graph-concepts:

 a) Tree concept: Facilities for tree inspection.

 b) MutableTree concept: Facilities for tree construction / destruction.

 c) MutablePropertyTree concept: Same as MutableTree concept but with
properties (like MutablePropertyGraph concept).

 d) NonCompactGraph concept: For graphs / trees that may contain invalid
vertices or edges (i.e., "holes").

https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_alg/tree_concepts.hpp

4) Boost Graph Library Tree adaptors. This is for using the
boost::adjacency_list to store a tree (and comply to tree concepts).
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_alg/bgl_tree_adaptor.hpp

5) Pooled Adjacency-list. This is a wrapper around the
boost::adjacency_list class which uses a method similar to Boost.Pool to
store vertices in a contiguous storage (boost::vecS) while keeping vertex
descriptors and iterators valid after removals.
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_alg/pooled_adjacency_list.hpp

Here are the some subjective issues to discuss:

 w.r.t.-3c) In my MutablePropertyTree concept, I have included removal
functions that extract the properties of the elements to be removed. This
can usually be implemented easily and provides symmetry w.r.t. to
element-adding functions (if you can provide properties when creating
elements, you should be able to retrieve them when removing elements).
Without this, you can either copy the properties before removing
the elements (needless copy and destruct), or you can std::move them out
before removing the elements (leaving zombie elements in the graph in the
meanwhile). The preferred option is to have the removal function move the
properties into a destination (e.g. back-inserter). I would argue that the
existing MutablePropertyGraph concept should include overloads for
recording properties during removals, this shouldn't break any existing
user-side code and be easily added to existing graph data structures.

 w.r.t.-3d) I have two issues with the NonCompactGraph concept:

 1) Invalid elements mostly (or only) show up from iterators. So, one
practical option is to have the iterators skip invalid elements. This
effectively makes a "non-compact" graph look "compact". This would make
this concept useless. However, iterators that must skip over invalid
elements cannot provide random-access. There are ways to get the best of
both worlds, such as introducing some "always-valid" iterators, which might
or might not be identical to the base iterators (zero-overhead) depending
on whether the graph is compact or not (a tag or meta-function might be
needed to identify this).

 2) A common operation with non-compact containers is to "re-pack" it.
Generally, the advantage of leaving holes in a container is to avoid
invalidating iterators. But, at certain points, one can decide to compact
the container again. In the non-compact implementations that I have, I have
included such functions, but never really needed them in practice (when
removals <= insertions). I wonder if such functions should be included in
the NonCompactGraph concept.

This is mainly what I propose to contribute back to the BGL (or any part of
it). I have, however, lots of other code that is peripheral or closely tied
to the BGL. Some is a bit more experimental at this stage, while other
things are too peripheral or too specific. You are welcome to browse my
library to see if anything else grabs your attention. See below for a short
list of a few specific items that might be of interest.

Cheers, (and pardon the lengthy email)
Mikael.

P.S.:
Other interesting items that I have developed that might be worth proposing:

6) Linked-tree. A classic linked-tree data structure. It has similar
signature as boost::adjacency_list and models the relevant BGL graph
concepts and the proposed tree concepts:
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_alg/linked_tree.hpp

7) Contiguous layout trees. These are fixed-arity (D-ary) trees that use a
breadth-first layout (similar to heaps) in contiguous memory. They model
the relevant BGL concepts and the proposed tree concepts.
 a) D-ary BF-tree uses one contiguous storage with vertices laid out in
breadth-first order. It works great, it's my work-horse tree-implementation
and the memory-locality it provides has been a major performance factor in
my code.
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_alg/d_ary_bf_tree.hpp
 b) D-ary COB-tree (Cache-Oblivious B-tree) uses a tree of moderately-sized
contiguous blocks with breadth-first layout within them. This thing is nice
in theory, but in practice it has been difficult to guarantee correctness
and to deliver good performance (it only out-performs the BF-tree when the
size of the tree is in the gigabytes range).
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_alg/d_ary_cob_tree.hpp

8) I wrote an AD* algorithm, which I modeled after the BGL's existing A*
search implementation. It's rather old code that I haven't done much with
for a while, but I'm willing to resurrect it if there is interest for it.
The fact that it is a dynamic / anytime / on-line graph algorithm makes it
a bit odd compared to the other existing algorithms in BGL (all static /
batch / off-line algorithms, AFAIK).
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_alg/adstar_search.hpp

9) I wrote a multi-graph template to overlay an adjacency-list (i.e.,
general "graph") and a tree (i.e., complying to the proposed tree
concepts). The point here is to have one set of vertices and two sets of
edges, one forming a general graph and one forming a tree. The motivation
is to: keep the graph and tree strongly synchronized by sharing the same
storage; and, benefit from cache-friendly tree layouts (e.g., BF-tree) when
using the general graph. My reservations with this are that the code is (1)
not be quite polished yet, (2) a bit too advanced / specific for the
general nature of the BGL, and (3) a bit convoluted to use (user-side code
is messy).
https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_alg/adj_list_tree_overlay.hpp

10) If you find anything else you like, we can discuss it. I mostly write
path-planning code and lots of numerical stuff. I have a nice
sampling-based motion-planning framework in place that builds upon the BGL,
and extended (and more mathematically sound) "Topology" concepts, as well
as space-partitioning trees and stuff like that:
https://github.com/mikael-s-persson/ReaK/tree/master/src/ReaK/ctrl/graph_alg
https://github.com/mikael-s-persson/ReaK/tree/master/src/ReaK/ctrl/path_planning
https://github.com/mikael-s-persson/ReaK/tree/master/src/ReaK/ctrl/topologies

-- 
Sven Mikael Persson