Interface ShortestPathSingleSource.Result<V,E>

Type Parameters:
V - the vertices type
E - the edges type
All Known Subinterfaces:
ShortestPathSingleSource.IResult
Enclosing interface:
ShortestPathSingleSource
public static interface ShortestPathSingleSource.Result<V,E>
A result object for the ShortestPathSingleSource problem.
Author:
Barak Ugav

  • Method Summary

    Modifier and Type
    Method
    Description
    E
    backtrackEdge(V target)
    Get the last edge on the shortest path from the source to the given target.
    double
    distance(V target)
    Get the distance to a target vertex.
    Path<V,E>
    getPath(V target)
    Get shortest path to a target vertex.
    Graph<V,E>
    graph()
    Get the graph on which the shortest paths were computed on.
    default boolean
    isReachable(V target)
    Check if a target vertex is reachable from the source.
    Set<V>
    reachableVertices()
    Get the set of vertices reachable from the source.
    default Graph<V,E>
    shortestPathTree()
    Get the shortest path tree.
    default Graph<V,E>
    shortestPathTree(boolean directed)
    Get the shortest path tree, optionally directed or undirected.
    V
    source()
    Get the source vertex from which all shortest paths were computed from.

  • Method Details

    • distance

      double distance(V target)
      Get the distance to a target vertex.
      Parameters:
      target - a target vertex in the graph
      Returns:
      the sum of the shortest path edges from the source to the target, or Double.POSITIVE_INFINITY if no such path found
      Throws:
      NoSuchVertexException - if target is not a vertex in the graph

    • getPath

      Path<V,E> getPath(V target)
      Get shortest path to a target vertex.
      Parameters:
      target - a target vertex in the graph
      Returns:
      the shortest path from the source to the target or null if no such path found.
      Throws:
      NoSuchVertexException - if target is not a vertex in the graph

    • backtrackEdge

      E backtrackEdge(V target)
      Get the last edge on the shortest path from the source to the given target.

      The backtrack edge is an in-edge of the given target vertex. The set of all backtrack edges of all vertices define the shortest path tree of the source, and each shortest path can be constructed from them.

      Parameters:
      target - a target vertex in the graph
      Returns:
      the backtrack edge, the last edge on the shortest path from the source to the given target, or null if there is no path to the target or the target is the source
      Throws:
      NoSuchVertexException - if target is not a vertex in the graph

    • isReachable

      default boolean isReachable(V target)
      Check if a target vertex is reachable from the source.
      Parameters:
      target - a target vertex in the graph
      Returns:
      true if the target is reachable from the source, false otherwise
      Throws:
      NoSuchVertexException - if target is not a vertex in the graph

    • reachableVertices

      Set<V> reachableVertices()
      Get the set of vertices reachable from the source.

      The source vertex itself is included in the returned set.

      Returns:
      the set of vertices reachable from the source

    • shortestPathTree

      default Graph<V,E> shortestPathTree()
      Get the shortest path tree.

      The shortest path tree is constructed from the vertices and edges used by any shortest path. It contains only the vertices reachable from the source, and for each vertex other than the source the graph will contains the edge that was used to reach it (see backtrackEdge(Object)). If there are \(k\) reachable vertices, the graph will contain \(k-1\) edges.

      The returned graph will be directed if the original graph is directed. In such case, the tree is directed from the source to the other vertices. To control the directionality of the returned graph, use shortestPathTree(boolean).

      Returns:
      undirected shortest path tree

    • shortestPathTree

      default Graph<V,E> shortestPathTree(boolean directed)
      Get the shortest path tree, optionally directed or undirected.

      The shortest path tree is constructed from the vertices and edges used by any shortest path. It contains only the vertices reachable from the source, and for each vertex other than the source the graph will contains the edge that was used to reach it (see backtrackEdge(Object)). If there are \(k\) reachable vertices, the graph will contain \(k-1\) edges.

      Parameters:
      directed - if true the returned tree will be directed. If the original graph was undirected and a directed tree is created, the edges in the tree will be directed from the source towards the other vertices
      Returns:
      un/directed shortest path tree

    • source

      V source()
      Get the source vertex from which all shortest paths were computed from.
      Returns:
      the source vertex

    • graph

      Graph<V,E> graph()
      Get the graph on which the shortest paths were computed on.
      Returns:
      the graph on which the shortest paths were computed on.