External Memory BFS
This page is no longer maintained. The External Memory BFS package will soon be shifted to a new place.
Our package provides I/O efficient implementation of external memory BFS algorithms: MR_BFS ([MR_BFS]) and MM_BFS ([MM_BFS]). Our implementation relies on the external memory library STXXL . The salient features of this implementation include:
- Extensive pipelining
- Exploiting disk-parallelism
- I/O efficient graph generators. Click here for the graph generator tool de-coupled from the main package.
- I/O efficient BFS decomposition verifier
For more details on this implementation, please refer to [EM_BFS_AJW].
Download
- External Memory BFS version 0.39
- Note that this code compiles with STXXL version 1.2.1 and g++-4.2, g++-4.3 and g++-4.4
- This code also compiles with the version in the STXXL trunk as of 31st October, 2009 and g++-4.2
- Also, note that this is an old version of the code. It does not contain the deterministic variant of Mehlhorn/Meyer's BFS algorithm or various heuristics used later to speed-up the code. It only includes the implementation of Munagala/Ranade's external memory BFS algorithm and the randomized variant of Mehlhorn/Meyer's BFS algorithm.
Our participation in DIMACS challenge
This project is also participating in the DIMACS challenge on shortest paths.
Participants:
Deepak Ajwani, Andreas Beckmann, Frederik Juul Christiani, Roman Dementiev, Rolf Fagerberg, Ulrich Meyer, Vitaly Osipov
Current Status:
Currently, we provide I/O efficient graph generators for generating large graphs in the format of DIMACS shortest path challenge . The generated graphs can also be used for shortest paths problems (though all the edge weights are one).