[BGL] Dijkstra/A* with large graph
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
participants (1)
-
Nicholas Mario Wardhana