Interface RoutingAlgorithm<E>

Type Parameters:
E - the edge type
All Known Implementing Classes:
Dijkstra
public interface RoutingAlgorithm<E>
An algorithm which can find a route between two vertices on an explorable graph. Support for predicate-based search is optional and not expected to be supported by directed search algorithms. Instances cam be converted to a typed routing algorithm using the toTypedRoutingAlgorithm method.
Author:
Lee A. Christie

  • Method Summary

    Modifier and Type
    Method
    Description
    <V> E
    cost(Explorable<V,E> graph, List<V> path)
    Reconstructs the total cost of a given path.
    static <V> Predicate<V>
    isOneOf(Collection<V> targets)
    Creates a predicate which checked whether an element is one of a specific given collection of non-null elements.
    static <V> Predicate<V>
    isOneOf(V... targets)
    Creates a predicate which checked whether an element is one of a specific given collection of non-null elements.
    <V> List<V>
    path(Explorable<V,E> graph, V source, Predicate<V> target)
    Finds a route from the specified source to the specified target(s) by predicate which returns true if a given vertex is a target.
    <V> List<V>
    path(Explorable<V,E> graph, V source, Predicate<V> target, E maxCost)
    Finds a route from the specified source to the specified target(s) by predicate which returns true if a given vertex is a target, within a given maximum cost.
    <V> List<V>
    path(Explorable<V,E> graph, V source, V target)
    Finds a route from the specified source to the specified target.
    <V> List<V>
    path(Explorable<V,E> graph, V source, V target, E maxCost)
    Finds a route from the specified source to the specified target within a given maximum cost.

  • Method Details

    • isOneOf

      static <V> Predicate<V> isOneOf(Collection<V> targets)
      Creates a predicate which checked whether an element is one of a specific given collection of non-null elements.
      Type Parameters:
      V - the vertex type
      Parameters:
      targets - the targets, not null, no null elements
      Returns:
      the predicate

    • isOneOf

      @SafeVarargs static <V> Predicate<V> isOneOf(V... targets)
      Creates a predicate which checked whether an element is one of a specific given collection of non-null elements.
      Type Parameters:
      V - the vertex type
      Parameters:
      targets - the targets, not null, no null elements
      Returns:
      the predicate

    • cost

      <V> E cost(Explorable<V,E> graph, List<V> path)
      Reconstructs the total cost of a given path.
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      path - a list of vertices describing each step in the path, not null
      Returns:
      the total cost of the path

    • path

      <V> List<V> path(Explorable<V,E> graph, V source, V target) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target.
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the target vertex, in graph, not null
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted, and the implementation supports interruption

    • path

      <V> List<V> path(Explorable<V,E> graph, V source, V target, E maxCost) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target within a given maximum cost.
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the target vertex, in graph, not null
      maxCost - the maximum cost, considered unlimited if null
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted, and the implementation supports interruption

    • path

      <V> List<V> path(Explorable<V,E> graph, V source, Predicate<V> target) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target(s) by predicate which returns true if a given vertex is a target.
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the criteria to identify a target vertex, in graph, not null
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted, and the implementation supports interruption

    • path

      <V> List<V> path(Explorable<V,E> graph, V source, Predicate<V> target, E maxCost) throws TargetUnreachableException, InterruptedException
      Finds a route from the specified source to the specified target(s) by predicate which returns true if a given vertex is a target, within a given maximum cost.
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the graph on which to route, not null
      source - the source vertex, in graph, not null
      target - the target vertex, in graph, not null
      maxCost - the maximum cost, considered unlimited if null
      Returns:
      a list of vertices describing each step in the path
      Throws:
      TargetUnreachableException - if no route could be found from source to target
      InterruptedException - if the thread is interrupted, and the implementation supports interruption