Is it possible to run a recursive function in parallel?

user_12168347 0
Viewed 363

I have a findAllPaths() function to find all possible paths in a graph (stored in matrix):

    public void findAllPaths(final Matrix matrix, final Index s, final Index d, HashMap <Index , Boolean> isVisited, Collection localPathList)
    {
        // Mark the current node
        isVisited.put(s, true);
        if (s.equals(d)) {
            this.pathsList.add(new ArrayList<>(localPathList));
            // if match found no need to traverse more till depth
            isVisited.put(s, false);
            return;
        }

        // Recur for all the vertices neighbors to current index
        for (Index i : matrix.getNeighbors(s)) {
            if (!isVisited.get(i)) {
                // store current node in path[]
                localPathList.add(i);
                findAllPaths(matrix, i, d, isVisited, localPathList);
                // remove current node in path[]
                localPathList.remove(i);
            }
        }

        // Mark the current node
        isVisited.put(s, false);
    }

I'm trying to make it run in parallel as much as possible.

Does anybody have an idea of how I can accomplish that?

forkjoinpool recursion parallel-processing java
1 Answers

You might want to use RecursiveTask or RecursiveAction of the java.util.concurrent package and run it in a ForkjoinPool. The general idea of these classes is that you decide in your code what portion of the work should be done in one thread. If the work is bigger than that portion, fork a part of the work to a new thread. To get the results of all threads, use join(). These classes use a work stealing algorithm: when a thread is done, it can steal work of another thread, so this is highly efficient for heavy number crunching like this.

One prerequisite of RecursiveTask or RecursiveAction, is that you should be able to split the work in parts, and that you know how to combine the finished parts to the final result. The factorial of a big number is one example that can be calculated using RecursiveTask: 10! can be split in (1 * 2 * 3 * 4 * 5) and (6 * 7 * 8 * 9 * 10). Both sub-results can be multiplied for the final result.

user_141477640
Related