Marije de Heus - Towards a Library of Parallel Graph Algorithms in Java

author:Marije de Heus
title:Towards a Library of Parallel Graph Algorithms in Java
keywords:Concurrency, graph algorithms, Java, termination detection
committee:dr.rer.nat. M. Weber
graduation date:January 2011



Despite the wide availability of multi-core processors and the popularity of Java, there is currently no library for parallel graph algorithms in Java available. Such a library would enable all Java programmers, especially those who work on the verification of programs and model checking to efficiently use graph algorithms. To find out what would be a good design for this library, we have made a start on it. We have created a general design for algorithms and graphs in the library. We have also implemented the reachability and connected components algorithms, both sequential and parallel. In this paper we describe the algo- rithms we have implemented and our design of the library, focusing on the design choices we made.