Parallel algorithms

[pnevyk]

It would be nice to provide implementations of parallel algorithms, especially if it would be possible to have them with the same API as their sequential counterparts. The goal is to try to implement a parallel algorithm in order to discover obstacles, rough edges, necessary API extensions/changes and helpful internals for implementing parallel algorithms in general.

A good candidate may be connected components. That will require implementing fundamentals such as parallel API on graph storages and parallel BFS.

Some resources I found online:

• https://en.wikipedia.org/wiki/Parallel_breadth-first_search
• https://people.csail.mit.edu/jshun/ligra.pdf + https://github.com/jshun/ligra
• https://shwestrick.github.io/2022/09/27/useful-races.html
• https://www.cs.cmu.edu/~guyb/paralg/paralg/parallel.pdf

[pnevyk]

Parallel algorithms may need more constraints on the graph (e.g., parallel iterators?) and these should not be required by default. Thus there should be a parallel() method on the algorithms builders which changes the constraints on the generics such that parallel algorithms are allowed. In other words, parallel algorithms should be opt-in instead of the default. Note that calling the parallel() method does not guarantee that a parallel algorithm will be used, that is up to the algorithm auto-selection.