net.automatalib.util.graphs

Class ShortestPaths

java.lang.Object

net.automatalib.util.graphs.ShortestPaths

public final class ShortestPaths
extends Object

Unweighted shortest path search in graphs.

This class offers an iterator-style approach to 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.

Author:

Malte Isberner

Method Summary

Modifier and Type	Method and Description
static <N,E> @Nullable Path<N,E>	shortestPath(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, Collection<?> targets)
static <N,E> @Nullable Path<N,E>	shortestPath(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, N target)
static <N,E> @Nullable Path<N,E>	shortestPath(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, Predicate<? super N> targetPred)
static <N,E> @Nullable Path<N,E>	shortestPath(IndefiniteGraph<N,E> graph, N start, int limit, Collection<?> targets)
static <N,E> @Nullable Path<N,E>	shortestPath(IndefiniteGraph<N,E> graph, N start, int limit, N target)
static <N,E> @Nullable Path<N,E>	shortestPath(IndefiniteGraph<N,E> graph, N start, int limit, Predicate<? super N> targetPred)
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, Collection<?> targets)
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, N target)
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, Predicate<? super N> targetPred)
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, N start, int limit, Collection<?> targets)
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, N start, int limit, N target)
static <N,E> Iterable<Path<N,E>>	shortestPaths(IndefiniteGraph<N,E> graph, N start, int limit, Predicate<? super N> targetPred)
static <N,E> Iterator<Path<N,E>>	shortestPathsIterator(IndefiniteGraph<N,E> graph, Collection<? extends N> start, int limit, Predicate<? super N> targetPred)

Methods inherited from class java.lang.Object

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

Method Detail

shortestPaths

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

shortestPaths

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

shortestPaths

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

shortestPaths

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

shortestPaths

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

shortestPaths

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

shortestPath

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

shortestPath

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

shortestPath

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

shortestPath

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

shortestPath

public static <N,E> @Nullable Path<N,E> shortestPath(IndefiniteGraph<N,E> graph,
                                                     Collection<? extends N> start,
                                                     int limit,
                                                     Collection<?> targets)

shortestPath

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

shortestPathsIterator

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