Graph Algorithms with fork/join

The equivalent of the hello world for parallel languages is the quicksort algorithm. The quicksort algorithm is based on the divide et impera principle, which makes it a good candidate for parallelization. In this article we will go past arrays and apply parallelism to more complex data structures such as graphs.

We will start by performing a DFS (Depth First Search). Given a starting node, visit all other reachable nodes. This algorithm can be adapted to solve many problems. Let’s see the basic form of this algorithm:

public void dfs(Node n) {
  Set<Node> visitedNodes = new HashSet<Node>();
  dfs(n, visitedNodes);
}

private void dfs(Node n, Set<Node> visitedNodes) {
  if (!visitedNodes.contains(n)) {
    doSomeStuff(n);
    visitedNodes.add(n);
    for (Node neighbor: n.getNeighbors()) {
      dfs(neighbor, visitedNodes);
    }
  }
}

The straightforward translation using the fork/join framework would look like:

public class DFS extends RecursiveAction {
  public DFS(Node n) { this(n, new HashSet<Node>()); }

  private DFS(Node n, Set<Node> visitedNodes) {
    this.n = n;
    this.visitedNodes = visitedNodes;
  }

  public void compute() {
    if (!visitedNodes.contains(n)) {
      doSomeStuff(n);
      visitedNodes.add(n);
      DFS[] subtasks = new DFS[n.getNeighbors().size()];
      for (int i = 0; i < n.getNeighbors().size(); i++) {
        subtasks[i] = new DFS(n.getNeighbors().get(i), visitedNodes);
      }
      forkJoin(subtasks);
    }
  }
}

You may have noticed that this code is actually not thread safe. If we have a subgraph with a diamond topology, we may end up visiting a node more than once. In order to fix that we must add a bit of synchronization. First of all we will mark a node as being visited even before visiting it, then we will define a critical section around the check and mark operations.

I will post the solution in my next post and talk a little bit about a parallel BFS (Breadth First Search).