On Sat, Jun 27, 2009 at 3:44 PM, Tim Keitt<tkeitt@gmail.com> wrote:
On Fri, Jun 26, 2009 at 6:33 PM, Sandeep Gupta <gupta.sandeep@gmail.com>wrote:
On Fri, Jun 26, 2009 at 4:15 PM, Jeremiah Willcock<jewillco@osl.iu.edu> wrote:
On Fri, 26 Jun 2009, Sandeep Gupta wrote:
Hi Jeremiah, The issue Tim brought up was regarding the case when the graph is not fully read in the main memory. Instead memory is allocated per out_edges invocation. For this to work the algorithm should not break range obtained from a out_edges call. However current implementation of dijkstra's does exactly that.
-- an example of range split: "depth_first_search(g, vis, color, *vertices(g).first);"
Tim proposed that he should be able to provide patch to fix such cases. I hope he has because for my current project I intend to process a graph stored externally.
What is wrong with the call to depth_first_search? That is getting a single vertex, not the whole range. I applied the kinds of things that were in his patch (not always in the same way), so his issues should be fixed. BGL was not built for out-of-core applications, though, so a lot of the changes are implementation details that can't really be relied upon. Are you trying to page in and out edge sets as needed, and that's why you need ranges to be used more consistently?
Yes, ideally i would like to page-in and -out the edge sets. Glad to know that these issues are fixed. I believe that as long as the calls to out_edges are indepenet/decoupled paging-in and -out should work. Although I will double check things once i get around to implementing
Sandeep,
Check the current trunk. I think all the "problem" cases are now fixed. Most notably, the iteration macros now only compare iterators from the same call to vertices, edges, et al. so algorithms that rely on those will work in cases where each call produces a new iterator range. The changes were motivated by storing edges in postgresql: https://launchpad.net/postgraph.
THK
Would do so. Thanks for clarifying and also for postgraph. -sandeep