[Boost-users] [BGL] Dijkstra/A* with large graph

Subject: [Boost-users] [BGL] Dijkstra/A* with large graph
From: Nicholas Mario Wardhana (mario.wardhana_at_[hidden])
Date: 2013-03-20 12:04:56

Hi all,

I am wondering if with Boost Graph Library, I can do either of these two things:

1) Merge several small graphs into one large graph
2) Save and load only a portion of a large graph at a time?

So the background is as follows. I have a large geometric graph (i.e.
a graph with 3D coordinate custom vertex properties), which I want to
use for path planning. The graph can be too large to be stored in the
memory (if I understand correctly, BGL uses STL data structures, which
have limits for the number of elements), so I implement the large
graph as multiple small graphs (let's just call them mini-graphs).
This way, I can save the mini-graphs to hard-disk, and load only the
necessary mini-graphs to plan the path (I have cost function to
determine the mini-graphs using Dijkstra). The problem is, this breaks
the connectivity of the original graph, and I also have to add some
points to two mini-graphs. Running Dijkstra/A* is consequently not
straightforward, since the starting and the goal nodes can be in
different mini-graphs.

The two aforementioned solutions can be used as a workaround. Using
approach #1, I can combine the chosen mini-graphs into one, on which I
can directly run Dijkstra/A*. In approach #2, I just have one variable
of graph, while the mini-graphs can just be implemented as extra
properties of the nodes and edges. This way, I can select which nodes
and edges to load from the files (e.g. if a node has a mini-graph ID
of 1, load the node).

Having said that, I don't know how to implement those approaches with
BGL. It seems to me that subgraph provides a hierarchically structured
graph, but is it possible to just load a subgraph without loading the
whole graph?

BTW, I am wondering if BGL has an external memory variant, like
Parallel BGL for multi-core environment? If not, is anybody aware if
there is such library (preferrably free to use for research purpose)?

Thank you!

Best regards,
Nicholas Mario Wardhana