Package net.automatalib.util.graph

Class ShortestPaths

java.lang.Object

net.automatalib.util.graph.ShortestPaths

public final class ShortestPaths
extends Object

Unweighted shortest path search in graphs.

This class offers an iterator-style approach to the shortest path search: the methods in this class generally return either an Iterator or an Iterable wrapped around an iterator which allows for enumerating all shortest paths to the given set of target nodes. The iterators implement this lazily, i.e., a call to the next() method of an iterator will continue the shortest path search on an as-needed basis.

Method Summary

Modifier and Type	Method	Description
static <N,E> @Nullable Path<N,E>	shortestPath(IndefiniteGraph<N,E> graph, N start, int limit, Predicate<? super N> pred)	Returns a shortest path from the start node to the first node that satisfies the given predicate, if available.
static <N,E> @Nullable Path<N,E>	shortestPath(IndefiniteGraph<N,E> graph, N start, int limit, N target)	Returns a shortest path from the start node to the target node, if available.
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, Collection<?> targets)	Returns a collection of shortest paths from the start nodes to the target nodes, if available.
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, Predicate<? super N> pred)	Returns a collection of shortest paths from the start nodes to all nodes that satisfy the given predicate, if available.
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, N target)	Returns a collection of shortest paths from the start nodes to the target node, if available.
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, N start, int limit, Collection<?> targets)	Returns a collection of shortest paths from the start node to the target nodes, if available.
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, N start, int limit, Predicate<? super N> pred)	Returns a collection of shortest paths from the start node to all nodes that satisfy the given predicate, if available.
static <N,E> Iterator<Path<N,E>>	shortestPathsIterator(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, Predicate<? super N> pred)	Returns an iterator of shortest paths from the start nodes to all nodes that satisfy the given predicate, if available.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

shortestPath

public static <N,E> @Nullable Path<N,E> shortestPath(IndefiniteGraph<N,E> graph,
                                                                 N start,
                                                                 int limit,
                                                                 N target)

Returns a shortest path from the start node to the target node, if available.

Type Parameters:

N - node type

E - edge type

Parameters:

graph - the graph

start - the start node

limit - a limit on the maximum path length

target - the target node

Returns:

a shortest path from the start node to the target node, null if such a path does not exist or exceeds the given limit.

shortestPath

public static <N,E> @Nullable Path<N,E> shortestPath(IndefiniteGraph<N,E> graph,
                                                                 N start,
                                                                 int limit,
                                                                 Predicate<? super N> pred)

Returns a shortest path from the start node to the first node that satisfies the given predicate, if available.

Type Parameters:

N - node type

E - edge type

Parameters:

graph - the graph

start - the start node

limit - a limit on the maximum path length

pred - the predicate that should be satisfied by the target node

Returns:

a shortest path from the start node to the first node that satisfies the given predicate, null if such a path does not exist or exceeds the given limit.

shortestPaths

public static <N,E> Iterable<Path<N,E>> shortestPaths(IndefiniteGraph<N,E> graph,
                                                                  N start,
                                                                  int limit,
                                                                  Collection<?> targets)

Returns a collection of shortest paths from the start node to the target nodes, if available.

Type Parameters:

N - node type

E - edge type

Parameters:

graph - the graph

start - the start node

limit - a limit on the maximum path length

targets - the target nodes

Returns:

a collection of shortest paths from the start node to the target nodes. May be empty if such paths do not exist or exceed the given limit.

shortestPaths

public static <N,E> Iterable<Path<N,E>> shortestPaths(IndefiniteGraph<N,E> graph,
                                                                  N start,
                                                                  int limit,
                                                                  Predicate<? super N> pred)

Returns a collection of shortest paths from the start node to all nodes that satisfy the given predicate, if available.

Type Parameters:

N - node type

E - edge type

Parameters:

graph - the graph

start - the start node

limit - a limit on the maximum path length

pred - the predicate that should be satisfied by the target nodes

Returns:

a collection of shortest paths from the start node to all nodes that satisfy the given predicate. May be empty if such paths do not exist or exceed the given limit.

shortestPaths

public static <N,E> Iterable<Path<N,E>> shortestPaths(IndefiniteGraph<N,E> graph,
                                                                  Collection<? extends N> start,
                                                                  int limit,
                                                                  N target)

Returns a collection of shortest paths from the start nodes to the target node, if available.

Type Parameters:

N - node type

E - edge type

Parameters:

graph - the graph

start - the start nodes

limit - a limit on the maximum path length

target - the target node

Returns:

a collection of shortest paths from the start nodes to the target node. May be empty if such paths do not exist or exceed the given limit.

shortestPaths

public static <N,E> Iterable<Path<N,E>> shortestPaths(IndefiniteGraph<N,E> graph,
                                                                  Collection<? extends N> start,
                                                                  int limit,
                                                                  Collection<?> targets)

Returns a collection of shortest paths from the start nodes to the target nodes, if available.

Type Parameters:

N - node type

E - edge type

Parameters:

graph - the graph

start - the start nodes

limit - a limit on the maximum path length

targets - the target nodes

Returns:

a collection of shortest paths from the start nodes to the target nodes. May be empty if such paths do not exist or exceed the given limit.

shortestPaths

public static <N,E> Iterable<Path<N,E>> shortestPaths(IndefiniteGraph<N,E> graph,
                                                                  Collection<? extends N> start,
                                                                  int limit,
                                                                  Predicate<? super N> pred)

Returns a collection of shortest paths from the start nodes to all nodes that satisfy the given predicate, if available.

Type Parameters:

N - node type

E - edge type

Parameters:

graph - the graph

start - the start nodes

limit - a limit on the maximum path length

pred - the predicate that should be satisfied by the target nodes

Returns:

a collection of shortest paths from the start nodes to all nodes that satisfy the given predicate. May be empty if such paths do not exist or exceed the given limit.

shortestPathsIterator

public static <N,E> Iterator<Path<N,E>> shortestPathsIterator(IndefiniteGraph<N,E> graph,
                                                                          Collection<? extends N> start,
                                                                          int limit,
                                                                          Predicate<? super N> pred)

Returns an iterator of shortest paths from the start nodes to all nodes that satisfy the given predicate, if available.

Type Parameters:

N - node type

E - edge type

Parameters:

graph - the graph

start - the start nodes

limit - a limit on the maximum path length

pred - the predicate that should be satisfied by the target nodes

Returns:

an iterator of shortest paths from the start nodes to all nodes that satisfy the given predicate. May be empty if such paths do not exist or exceed the given limit.