A stream processing-based algorithm for maintaining minimum spanning forests of evolving graphs

Abstract

In this work we introduce a concurrent/parallel adaptation of Kruskal algorithm based on the dynamic pipeline approach. This is, the input (undirected) graph is given by a stream of weighted edges and it is dynamically created and maintained in a distributed way along a pipeline of stateful stages. To be concrete, firstly an initial graph is created and then, whenever the graph evolves because of edges are added, removed or updated, the minimum spanning tree (forest) according to the current graph can be computed and output immediately. Moreover, we provide a working implementation in the Go programming language. Go is suitable to dynamic pipelines’ implementations thanks to its communication channels and co-routines. We show experimentally that our algorithm scales well to a large number of processes and that it is competitive against the classic sequential Kruskal algorithm and a well known parallelized version of the Kruskal algorithm. Our experimental study is done for a large class of dynamic random graphs –including several densities and sizes– and some real dynamic graphs.

This work has been funded by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21.

Peer Reviewed

Postprint (published version)