Graphs and graph algorithms are at the heart of the solutions to many real-world problems. Unsurprisingly, graph algorithms have been studied extensively for many years, and one would expect that by now correct, robust and well-designed implementations in all major programming languages are available at least for the classic, well-known algorithms.
We will pick the Java language as an example here: Several libraries with graph algorithms are available for Java. Some of them focus on graph visualization and layout, while others provide algorithms. However, none of these libraries seems to accommodate current and future multi-core processors, or a cluster of (distributed-memory) computers.
The goal of this project is to produce a Java library of existing parallel graph algorithms.
The algorithms should not be tied to a particular graph representation, so that already existing programs can still benefit from the parallel computing power of today's processors, without:
The reason is that both of these options are quite costly: they introduce new sources of errors, and entail a significant amount of development time.
For reasons of reusability, you should also evaluate whether one of the existing Java graph libraries can be retrofitted with parallel graph algorithms. If not, design a new library from scratch, with parallel algorithms in mind from the start.
For inspiration on design questions, you can review parallel graph libraries in other languages.
Select a number of general-purpose parallel (shared-memory) graph algorithms from the literature, e.g.: parallel breadth-first search, depth-first search with a work-stealing approach, parallel detection of strongly-connected components (SCCs), etc.. Evaluate whether these algorithms can be implemented with Java concurrency primitives (Threads, JCSP, ...), in a way compatible to an existing Java graph libraries.
If none of the existing libraries can be reused, design a new library, under the following considerations:
You should consider the interface design as the most important part, and the actual implementations merely as a proof that the chosen interfaces are well-designed.
A working knowledge of the Java language.