On Mon, 9 Feb 2009, Andrew Sutton wrote:
Actually, I wasn't defining my own graph type. I've been using the CSR template class which was definitely an improvement over the adjacency list in terms of memory usage. I definitely have no use for adding and removing vertices on the fly. However, I am willing to look into defining my own graph. Do you think it's not beyond someone who is only a mediocre C++ programmer? I've been reading the doc site, but I haven't found any information about how to create my own graph. Could you please tell me where to look?
I think your best bet may be to modify the CSR graph types to use something other than size_t. Copy it, rename the type, and change it to suit your needs. That's close enough to creating your own graph type :)
I'm not entirely convinced that the benefits will outweigh the cost here. Maybe you'll save a couple MB, but you might do so at the expense of performance.
If your graph is purely a grid, you can also just create an implicit graph that takes no space (at least for the graph structure). In this case, your vertex_descriptor would just be the grid coordinates, and the edge_descriptor would be a source vertex and an output index. You could save a large amount of memory for large graphs that way, since the structure of the graph would not be stored at all, and you could trivially convert between vertex_descriptors and positions in the grid. Your properties would still take memory if you have some, of course. There is an example of how to create a graph like you want in chapter 9 of the BGL book (your grid is very similar to the knight's tour problem in that chapter). -- Jeremiah Willcock