Chris Russell wrote:
Erik, how huge is huge? Heap requirements in excess of 2^64 bytes huge? If so, that's one _massive_ graph and some supercomputer programmer will have to help.
Well, 2^64 bytes is several orders of magnitude larger than I had in mind. I guess my graph would be something like 1000 GB tops. It's still a pretty massive graph though...
I think the term you're looking for is "External-Memory Graph Algorithms".....googling turns up some stuff which may be interesting. Note that this is an active area of research so it may not be easy to make these algorithms work with BGL....
If not, then why not leverage the full virtual memory space allocated to your process and let the OS worry about paging the data in/out of physical memory?
This is definitely an alternative, but my worry is that this solution might be much slower than it needs to be. When swapping back and forth, the OS doesn't really know what's going on, whereas I might have the knowledge of the order in which the different parts of the graph are processed etc.
Letting the OS worry about paging is usually not a good idea if you have some advance knowledge on how you'll use your data. Running times can be decreased by several orders of magnitude by paying attention to how memory is used. Check out papers on cache aware/cache oblivious/external memory/ algorithms for further details.... rgds Jeppe