Return to Answer

• Many graph algorithms use a queue or a stack, to store partial paths to be extended further. Some version of DFS hide the stack in the call stack.
  If there is a queue based version of the algorithm use it: Without queue, it's more difficult to share work, and you need to find other ways to apply the following tricks.
• The trick for easy parallelization is to distribute queued elements for being processed by available processing nodes. So instead of extending the explored path one edge at a time, you'd extend N nodes in the same time in parrallel. Using queues to distribute work is the easiest way to parllelize work: one process manages the queue, and N worker-processes that dequeue the the elements, process them and enqueue the results.
• Most graph traversal algorithms are inherently sequential. Parallelizing them means that you might process elements in the queue that would never be processed in the sequential version. So there is a tradeoff to find between adding processing nodes (with the risk of doing unnecessary work) and having less nodes (but going back to sequential like performance).

So be prepared to make measurements and validate your approach.
A long time ago, I had for example to paralelize A* on a limited set of geographical data. Measurements showed that adding up to 4 nodes increased performance, but beyond 4, the performance decreased again, just because of the additional communication overhead and the unnecessary extension of unpromising partial paths.

• First, building your MST already requires you to explore every node
• Second, graph exploration algorithms have to unfold node by node and edge by edge.
  When you start at the orange node, you don't know how many branches there will be in the MST nor which part of the graph to assign to which processor.

With the approach proposed above, you'd enqueue the first node (orange 8  ). A free process dequeues it, prolonges the path and enqueue the single result (O8->8). As we are in a "corridor", the same must happen again (O8->8->8) before we have more choices and more parallelism. then a free process dequeues the only path in the queue, extends it: we have 2 alternatives that will be enqueued: O8->8->8->6 and 08->8->8->2. Now a first processor will take the first path in the queue (...->6), another free processor will take the second path (...->2), and both processors extend in parallel their nodes. If both processes have the same speed, we now have 5 path in the queu and upt to 5 processors busy, and so on.

Of course, you'll notice that O8->8->8->6->bottom2 and O8->8->8->2 arrive at the same point. In your exploration you must avoid such duplicates. This can be done by marking visited nodes to avoid double visit. This cannot be done safely in the processors because of synchronisation issues. So you may implement this when you enqueue the results and discard any path that arrives at an already visited node.

With this approach, everytime there's a branch, you'll use more pralelism until you reach the maximum processors. However in your simple graph, I think that you'll never have more than 5 processors active at the same time  , that 's 6 processes if you add the queue manager.

THere are any other parallelization of task possible, for example sorting the queue, filtering out the doubled targets, etc...

If your graph topology is a bottleneck for parallization, you may introduce some randomness. Take K random nodes and start exploration from there, when enqueing in the global queue, any path with nodes in common would be merged. As soon as on of the processor gets iddle, pick a new random unvisited node and add it to the queue.

This variant adds a small inefficiency: some nodes might get visited twice, once from each connection. It's those that lead to a path merger. But it keeps all the processors as much busy as possible. In your example, most of the time 8 processors will work instead of a maximum of 5.

And this is why in my original answer, I adviced to carefully measure performance to find teh post suitable parallization strategy (which might also depend on the graph topology).

• Many graph algorithms use a queue or a stack, to store partial paths to be extended further. Some version of DFS hide the stack in the call stack.
  If there is a queue based version of the algorithm use it: Without queue, it's more difficult to share work, and you need to find other ways to apply the following tricks.

• The trick for easy parallelization is to distribute queued elements for being processed by available processing nodes. So instead of extending the explored path one edge at a time, you'd extend N nodes in the same time in parrallel. Using queues to distribute work is the easiest way to parllelize work: one process manages the queue, and N worker-processes dequeue the elements, process them and enqueue the results.

  

• Most graph traversal algorithms are inherently sequential. Parallelizing them means that you might aggressively process elements in the queue that would never be processed in the sequential version. So there is a tradeoff to find between adding more workers (with the risk of doing unnecessary work) and having less workers (but going back to sequential like performance).

So be prepared to make measurements and validate your approach.
A long time ago, I had for example to parallelize A* on a limited set of geographical data. Measurements showed that adding up to 4 worker-nodes increased performance, but beyond 4, the performance decreased again, just because of the additional communication overhead and the unnecessary extension of unpromising partial paths.

• First, building your MST already requires you to explore every node
• Second, graph exploration algorithms have to unfold node by node and edge by edge.
  When you start at the orange node, you don't know how many branches there will be in the MST nor which part of the graph to assign to which worker.
  

With the approach proposed above, you'd enqueue the first node (orange 8). A free worker dequeues it, prolonges the path and enqueue the single result (O8->8). As we are in a "corridor", the same must happen again (O8->8->8) before we have more choices and more parallelism. Then a free worker-process dequeues the only path in the queue, extends it: we have 2 alternatives that will be enqueued: O8->8->8->6 and 08->8->8->2. Now a first worker will take the first path in the queue (...->6), another free worker will take the second path (...->2), and both workers extend in parallel their nodes. If both workers have the same speed, we now have 5 paths in the queue and up to 5 workers busy, and so on.

Of course, you'll notice that O8->8->8->6->bottom2 and O8->8->8->2 arrive at the same point. In your exploration you must avoid such duplicates. This can be done by marking visited nodes to avoid double visit. This cannot be done safely in the workers because of synchronisation issues. So you may implement this when you enqueue the results and discard any path that arrives at an already visited node.

With this approach, everytime there's a branch, you'll use more pralelism until you reach the maximum number of workers. However in your simple graph, I think that you'll never have more than 5 workers active at the same time, that's 6 parallel processes if you add the queue manager.

There are other parallelization of task possible, without adding workers, for example parrallelizing the sorting of the queue, the filtering of doubled targets, etc...

If your graph topology is a bottleneck for parallization, you may introduce some randomness. Take K random nodes and start exploration from there; when enqueuing in the global queue, any path with nodes in common would be merged. As soon as one of the processor gets iddle, pick a new random unvisited node and add it to the queue.

This variant adds a small inefficiency: some nodes might get visited twice, once from each connection. It's those that lead to a path merger. But it keeps all the processors as busy as possible. In your example, most of the time 8 processors will work instead of a maximum of 5 before.

And this is why in my original answer, I adviced to carefully measure performance, to find the most suitable parallelization strategy (which might also depend on the graph topology).

Edit: considering that all the edges are same-weighted, the risk of processing suboptimal nodes in the queue are significantly reduced if you use DFS. So if you can modify BFS in a way to make sure that it ends the search if and only if all the nodes were explored, go for it;

Initial answer to the initial question

General approach when parallelizing graph exploration

Edit: considering that all the edges are same-weighted, the risk of processing suboptimal nodes in the queue are significantly reduced if you use DFS. So if you can modify BFS in a way to make sure that it ends the search if and only if all the nodes were explored, go for it;

Example based on your new graph example.

Your visual reasoning about branches of the MST is not valid for solving your problem:

• First, building your MST already requires you to explore every node
• Second, graph exploration algorithms have to unfold node by node and edge by edge.
  When you start at the orange node, you don't know how many branches there will be in the MST nor which part of the graph to assign to which processor.

With the approach proposed above, you'd enqueue the first node (orange 8 ). A free process dequeues it, prolonges the path and enqueue the single result (O8->8). As we are in a "corridor", the same must happen again (O8->8->8) before we have more choices and more parallelism. then a free process dequeues the only path in the queue, extends it: we have 2 alternatives that will be enqueued: O8->8->8->6 and 08->8->8->2. Now a first processor will take the first path in the queue (...->6), another free processor will take the second path (...->2), and both processors extend in parallel their nodes. If both processes have the same speed, we now have 5 path in the queu and upt to 5 processors busy, and so on.

Of course, you'll notice that O8->8->8->6->bottom2 and O8->8->8->2 arrive at the same point. In your exploration you must avoid such duplicates. This can be done by marking visited nodes to avoid double visit. This cannot be done safely in the processors because of synchronisation issues. So you may implement this when you enqueue the results and discard any path that arrives at an already visited node.

With this approach, everytime there's a branch, you'll use more pralelism until you reach the maximum processors. However in your simple graph, I think that you'll never have more than 5 processors active at the same time , that 's 6 processes if you add the queue manager.

The worst case is when you graph is a long chain of nodes, each one linked only with a successor. It will run with 2 active processes only: worse than sequential because of the overhead of work distribution.

Other variants

THere are any other parallelization of task possible, for example sorting the queue, filtering out the doubled targets, etc...

If your graph topology is a bottleneck for parallization, you may introduce some randomness. Take K random nodes and start exploration from there, when enqueing in the global queue, any path with nodes in common would be merged. As soon as on of the processor gets iddle, pick a new random unvisited node and add it to the queue.

This variant adds a small inefficiency: some nodes might get visited twice, once from each connection. It's those that lead to a path merger. But it keeps all the processors as much busy as possible. In your example, most of the time 8 processors will work instead of a maximum of 5.

And this is why in my original answer, I adviced to carefully measure performance to find teh post suitable parallization strategy (which might also depend on the graph topology).

Your question is very broad. First let's give a name to your problem: you want to build a minimum spanning tree of your graph. And when you say collaboratively, I undestand with concurrent processes. For this there are knwon algorithms.

More generally, for graph traversal problems that you want to parralelize :

• If there is a queue based algorithm use it: the unfinished potential path are in general put in a queue according to a specific order. It's then easy to parllelize having one process managing the queue, and N worker processes that dequeue the next potential path process it and enqueu the resulting extended path.
• Without queue, it's more difficult to share work, and you need to find other ways to parallelize.
• Most graph traversal algorithms are inherently sequential. Parallelizing them means that you might extend a potential path that would never be extended in the sequential version. So there is a tradeoff to find between adding processing nodes with the risk of doing unnecessary processings and having less nodes but going back to sequential like performance.

So be prepared to make measurements to validate your approach.
A long time ago, I had for example to paralelize A* on a limited set of geographical data. Measurements showed that adding up to 4 nodes increased performance, but beyond 4, the performance decreased again, just because of the additional communication overhead and the unnecessary extension of unpromising partial paths.

Important remark: the question was significantly edited. The original question only mentioned the need to explore all the nodes of the graph without mentioning MST. Despite it is now obsolete, I leave the first paragraph, because it linked to parallel algorithms solving the problem.

Your question is very broad. First let's give a name to your problem aiming at exploring all the edges: you want to build a minimum spanning tree of your graph. And when you say collaboratively, I undestand with concurrent processes. For this there are knwon parallel algorithms that are proven to work.

More generally, you may apply the following advices for parallelizing graph exploration and traversal problems:

• Many graph algorithms use a queue or a stack, to store partial paths to be extended further. Some version of DFS hide the stack in the call stack.
  If there is a queue based version of the algorithm use it: Without queue, it's more difficult to share work, and you need to find other ways to apply the following tricks.
• The trick for easy parallelization is to distribute queued elements for being processed by available processing nodes. So instead of extending the explored path one edge at a time, you'd extend N nodes in the same time in parrallel. Using queues to distribute work is the easiest way to parllelize work: one process manages the queue, and N worker-processes that dequeue the the elements, process them and enqueue the results.
• Most graph traversal algorithms are inherently sequential. Parallelizing them means that you might process elements in the queue that would never be processed in the sequential version. So there is a tradeoff to find between adding processing nodes (with the risk of doing unnecessary work) and having less nodes (but going back to sequential like performance).

So be prepared to make measurements and validate your approach.
A long time ago, I had for example to paralelize A* on a limited set of geographical data. Measurements showed that adding up to 4 nodes increased performance, but beyond 4, the performance decreased again, just because of the additional communication overhead and the unnecessary extension of unpromising partial paths.

Edit: considering that all the edges are same-weighted, the risk of processing suboptimal nodes in the queue are significantly reduced if you use DFS. So if you can modify BFS in a way to make sure that it ends the search if and only if all the nodes were explored, go for it;