How to traverse a graph in parallel with 2 or n processes

Question

I am searching on the internet in order to find some algorithm that can traverse a graph in parallel using 2 or n processes without one process stepping into a previously visited node of the other so I can speed up the total scanning task of the whole graph, but I can't find anything. Is there any algorithm that can help me do such task in parallel? is it worth it?

Note : n processes share the same memory of visited and tovisit nodes

thank you

Answer 1

You can try the consumer-producer model for traversing the graph - but with some modifications from the pure model:

• Read and write to the queue in blocks, rather then element at a time, also update the visited set in blocks. It will save you the synchronization time - which will be needed to be done less frequently.
• When you do modify the queue (and visited set) - you should do some extra work to make sure you don't add data that was already visited since the set was last checked.

Note that with this approach - you are more then likely to search some vertices a few times - but you can bound it with the frequency the queue and visited set are updated.

Will it worth it? It is hard to say in these things - it is dependent on a lot of things (graph structure, size, queue implementation, ...).

You should run a few tests and try to fine tune the parameter for "how often to update", and check which is better empirically. You should use statistical tools (wilcoxon test is the de-facto standard for this usually) and determine if one is better then the other.

Answer 2

Unless the bulk of the time is spent on actual traversal, you could traverse the graph on a single thread, and queue up the work at each node to be processed in parallel from multiple processes. Once you have work in a queue, you can use a simple producer-consumer model.