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

Subject: Re: [boost] [graph] A few additions to propose to BGL
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-05-21 13:17:10

On Sun, 19 May 2013, Mikael Persson wrote:

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

This seems really nice.  One issue is that your changes will need to be 
under the Boost license for them to be included.  There are more comments 
interspersed through the rest of the email.

> 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

What is subobject_put_get_helper for?  I can't tell what it is doing. 
Could you please briefly explain the others?  How does self_property_map 
differ from typed_identity_property_map; I see that yours returns a 
reference rather than a value, but is that important?

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

These look very useful, and seem intuitively "right" to me.  What do you 
think of Boost.PropertyTree?  It has a different domain than your 
concepts, but is also trying to represent trees.  There also seem to be 
(limited) tree concepts in Boost.Graph; see <boost/graph/tree_traits.hpp> 
and <boost/graph/graph_as_tree.hpp>.  They do not appear to be heavily 
used, though, and yours look to be cleaner and more capable.

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

The usual technique for this is to use a filtered_graph, which keeps the 
original graph's vertex and edge indexes (with not all values valid) and 
filters out the removed vertices in traversals.  Could you please compare 
your approach to that?

> 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

Those two items would both be very useful.

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

In which situations do you need random access iteration?  Are there places 
that you would use the non-compact iterators that are not immediately 
followed by filtering the vertices manually?

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

It is fine to have functions in your implementation that are not part of 
the concept; it just means that code that uses them would rely on that 
particular type rather than the general concept.  You could also have a 
refining concept that adds the extra functionality.

> 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

Can this tree use external storage?  The current d-ary heap in BGL 
doesn't, and that causes problems for some users.

> 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

Would this (and the one above) be useful for people who need BFS and DFS 
trees that allow going from parents to children, not just the other way?

> 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

There is an incremental connected components function, but having more 
dynamic algorithms would be good in general.

> 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

I'll take a look at these last two items and think about them more.

-- Jeremiah Willcock