0
$\begingroup$

Background

Definitions (as used here):

$\qquad$single-source: for path finding, an algorithm is single-source if it searches from a given node.

$\qquad$multi-target: for path finding, an algorithm is multi-target if it searches for at least one path to each of the specified targets

$\qquad$multi-path: for path finding, an algorithm is multi-path if it returns at least one path - if one exists - but at most $n$ where $n$ is the number to find.

$\qquad$max-depth: for path finding, an algorithm has max-depth if the length of the returned path(s) is less than or equal to $d$ where $d$ is the specified depth.


Notation:

$k$ - max depth

$t$ - the target set $\{t_1,\dots,t_{\lvert t\rvert}\}$

$s$ - the source vertex

$n$ - number of paths to find per target


Goal of the question: To determine the best (or a sufficiently good) approach for finding up to $n$ paths for each of target ($t_i$) within a max-depth of $k$ for a single-source $s$ in a directed graph. In addition $n$ paths from each of the targets to $s$ within a max-depth of $k$.

an example function call should be:

find_path(G, s, t, n, k)

With the aforementioned goal in mind, we can consider some interesting questions.

For example, is it necessarily always faster to parallelize over the targets (e.g. single-source, multi-path, single-target of max depth) than searching for multi-targets? My intuition hesitantly says yes... however in some cases it might not make sense. For example, in greedy breadth first search (if there are never duplicates of values used in the heuristic), the frontier will always be the same, regardless of target. In such cases, why would one parallelize over the multiple targets, when to find any target, $t_i$, one must first visit all targets that have a "better" path than $t_i$ and continue until it finds all targets "worse" than $t_i$.

Many algorithms are focused on the "best-path" problem. In this case, modifying them can be difficult to get the $n$ best paths.

In a question on stack overflow Variants of a star the user attempts something similar by constructing multiple variants of A*. However, the multi-path is also left out.

When the $n$-best paths are not considered, but just $n$ paths. Similarly, making all of these adjustments to depth-first-search is fairly simple (below multi-target is left out as I think parallel DFS is faster than multi-taget):

Depth first search pseudo code

dfs(source, target, depth, num_p, timeout):
    paths_found = []
    dfs_recur(source, target, 1, depth, num_p, [], paths_found, now, timeout)

dfs_recur(current, goal, current_depth, max_depth, number_of_paths_to_find, current_path, paths_found, start_time, timeout):
    // timeout
    if now - start_time > timeout:
        return 

    current_path.push(current)
    // too deep
    if current_depth > max_depth:
        current_depth.pop()
        return 

    // found
    if current == goal:
        if len(paths_found) < number_of_paths_to_find:
            paths_found.push(current_path)
        current_path.pop()
        return 

    // hack to not miss goal in current depth
    elif goal in V[current]['successors']:
        current_path.push(goal)
        if len(paths_found) < number_of_paths_to_find:
            paths_found.append(current_path)
        current_path.pop()
        return 

    // normal dfs
    else:
        for n in V[current]['successors']:
             dfs_rec(n, goal, current_depth + 1, max_depth, number_of_paths_to_find, current_path, paths_found, start_time, timeout)

I have looked into the following:

- Finding Top K Shortest Simple Paths with Improved Space Efficiency
- Eppstein k-best
- A* and some of its many variants e.g. A* Prune
- A K-Best Paths Algorithm for Highly Reliable Communication Networks
- Ant colony / Bee sensor based approaches
- bi-directional approaches
- greedy variants of DFS and BFS (with and without max depth cut offs)
- Yen's algorithm with Lawler's improvements

but as none of these algorithms single handily solve my problem it is hard to determine which algorithm(s) to use (and if in parallel).


Specific use case:

Suppose you have a fairly large, sparse, but highly connected graph, $\lvert V \rvert\approx50000$, $\lvert E \rvert\approx2000000$. So in the Adjacency Matrix (AM) the sparsity is about 0.0008 and on average each vertex has 40 connections.

Then prior to the search, one calculates the extended neighborhood on the source vertex to the scope of the max depth. In other words, construct the sub-graph, where ever vertex can be reached within a path of $k$ ("scope") and only those edges (e.g. only the predecessors of predecessors of the source, and only the successors of the successors of the source).

This might sound counter intuitive. If I am searching for paths of max length $k$, why precompute the extended neighborhood (which has all putative paths of length $\leq k$) when I could search for the paths directly. I am not sure about this, but calculating the extended neighborhood is fairly time efficient and I believe the time use to limit the scope (often) reduces the run time of the path finding more than if one were to run the path finding on the large graph. e.g. limiting to a scope of three can result in a sub-graph of $20,000$ vertices and $980,000$ edges. Since many algorithms are quadratic (or $\lvert E \rvert + \lvert V\rvert \log \lvert V\rvert$), I think the reduction may be worth it. (I have no concrete proofs or bounds to demonstrate this).

Question

What is the best approach to finding $n$ best paths to each target in $t$ from $s$ of max path length $k$? (parallelization allowed)

$\endgroup$
  • $\begingroup$ Why have you rejected Eppstein's algorithm and Yen's algorithm? Your explanation ("it is hard to determine which algorithm to use") is hard to follow -- one way to determine which one to use is to implement each of them and benchmark them to see how well they perform on your particular workload. $\endgroup$ – D.W. Mar 28 '18 at 21:52
  • $\begingroup$ If you want to give us suggestions that are a fit for your particular size of graph, it would help to tell us the approximate value of $k$ and $n$ in your workload. $\endgroup$ – D.W. Mar 28 '18 at 21:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.