CGMgraph/CGMlib: Implementing and testing CGM graph algorithms on PC clusters

In this paper, we present CGMgraph, the first integrated library of parallel graph methods for PC clusters based on CGM algorithms. CGMgraph implements parallel methods for various graph problems. Our implementations of deterministic list ranking, Euler tour, connected components, spanning forest, and bipartite graph detection are, to our knowledge, the first efficient implementations for PC clusters. Our library also includes CGMlib, a library of basic CGM tools such as sorting, prefix sum, one to all broadcast, all to one gather, h-Relation, all to all broadcast, array balancing, and CGM partitioning. Both libraries are available for download at http://cgm.dehne.net