Sub-graphs for Boost Graph Library Implementations

[marip8]

Background

After making a .dot file serialization for the graph in the BGL graph in #68 that utilizes sub-graphs for the visualization, I thought it might be beneficial to actually represent the planning graph as a collection of sub-graphs under the hood. This representation would be similar to rungs in the ladder graph implementation, where each sub-graph would be the collection of vertices created by a state sampler.

Issue

I implemented the solution here and discovered a subtlety of sub-graphs that might discourage us from using them. When boost::add_vertex is called with a sub-graph, a vertex and its properties are added to both the sub-graph itself and all parents of the sub-graph (see documentation of add_vertex in non-member functions). This results in duplication of the vertex properties at the sub-graph and parent levels, and the duplicated properties are not connected. This poses several problems:

1. 2x more memory (or more, depending on the depth of the sub-graphs) is required because of the duplication of vertex properties
   • I only tested this for vertices with bundled properties. I'm not sure if this is true for properties that are contained within the graph, but I imagine it would be the same
2. Two sets of properties for the same conceptual vertex exist and it becomes unclear which to use. If the properties are changed through the sub-graph, only the properties of the vertex stored in the sub-graph get changed, and likewise for a parent graph
3. If a search is used to update bundled properties (like vertex distance or color), only the properties of the vertices in the graph that was searched get changed. If the parent graph was searched, the properties of the sub-graph vertices do not get changed.
   • In my specific case, I performed a search on the parent graph, and then tried to find the lowest cost vertex in the sub-graph representing the last rung. All of the vertices in the sub-graph of the last rung had default values for all properties because I had only modified properties in the parent graph and performed the search on the parent graph.

Recommendation

We should not try to use sub-graphs as the representation of BGL planning graphs until we can find a solution that doesn't duplicate vertex properties