author: Jochem Schutte
title: Designing a Library of (Parallel) Graph Algorithms
keywords:
topics: Algorithms and Data Structures , Graphs
committee: Marieke Huisman ,
Jaco van de Pol
end: June 2013

Description

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.

Goal

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:

  1. having to reimplement any of the parallel algorithms, or
  2. changing existing core data structures.

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.

Tasks

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:

  • Design homogeneous interfaces for the chosen graph algorithms and justify your design decisions.
  • Provide algorithm templates (parametrized or abstract classes) and default implementations adhering to these interfaces.
  • Specify algorithms such that vertex (edge) markings (commonly needed in graph algorithms) can be maintained either external to a vertex (edge), or internal (stored directly with a vertex).
  • Consider mutable and persistent graph data structures.
  • Use modern Java features to your advantage.
  • Structure the library in such a way that specific parts can be used independently of the rest. Graph algorithms are often spanning different usage domains, and any given project likely uses only a small portion of the provided functionality.

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.

Requirements

A working knowledge of the Java language.

Related Work

Additional Resources

  1. The paper