Package com.jgalgo.alg.shortestpath

Interface VoronoiAlgo.Result<V,E>

Type Parameters:
V - the vertices type
E - the edges type
All Known Subinterfaces:
VoronoiAlgo.IResult
Enclosing interface:
VoronoiAlgo
public static interface VoronoiAlgo.Result<V,E>
A result object of VoronoiAlgo computation.

The result object is firstly a valid IVertexPartition of the graph. The partition is defined by the sites. Each 'block' contains all the vertices that are closer to the site of the block than to any other site. If some vertices are unreachable from any sites, the partition will contain an addition block with index siteNumber+1 that contains all these vertices. The result object itself does not extends the VertexPartition interface, but the partition is accessible by the partition() method.

In addition to holding a partition, the result object also contains the distance of each vertex from its site, and the shortest path from the sites to the vertices. Note that the direction of the distances and paths (in case of a directed graph) is from the sites to the vertices. If the other direction is needed, consider passing a reversed view of the original graph by using Graph.reverseView().

Author:
Barak Ugav
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    V
    blockSite(int block)
    Get the site vertex of a block.
    double
    distance(V vertex)
    Get the distance of a vertex from its site.
    Path<V,E>
    getPath(V target)
    Get the shortest path of a vertex from its site.
    VertexPartition<V,E>
    partition()
    Get the partition of the graph to blocks where each block contains the vertices which are closest to a single site.
    V
    vertexSite(V vertex)
    Get the site vertex of a vertex.

  • Method Details

    • partition

      VertexPartition<V,E> partition()
      Get the partition of the graph to blocks where each block contains the vertices which are closest to a single site.
      Returns:
      the partition of the graph to sites blocks

    • distance

      double distance(V vertex)
      Get the distance of a vertex from its site.

      Note that the direction of the distances and paths (in case of a directed graph) is from the sites to the vertices.

      Parameters:
      vertex - a target vertex
      Returns:
      the shortest distance from any site to the target vertex, or Double.POSITIVE_INFINITY if the target vertex is unreachable from any site

    • getPath

      Path<V,E> getPath(V target)
      Get the shortest path of a vertex from its site.

      Note that the direction of the distances and paths (in case of a directed graph) is from the sites to the vertices.

      Parameters:
      target - a target vertex
      Returns:
      the shortest path from any site to the target vertex, or null if the target vertex is unreachable from any site

    • blockSite

      V blockSite(int block)
      Get the site vertex of a block.

      The Voronoi cells are defined by the sites. Each 'block' contains all the vertices that are closer to the site of the block than to any other site. This method return the site vertex of one of the blocks [0, numberOfBlocks()).

      In case some vertices are unreachable from any sites, the partition will contain an addition block with index siteNumber+1 that contains all these vertices. This method will return null for this block.

      Parameters:
      block - index of a block
      Returns:
      the site vertex of the block, or null if the block is the unreachable block

    • vertexSite

      V vertexSite(V vertex)
      Get the site vertex of a vertex.

      The Voronoi cells are defined by the sites. Each 'block' contains all the vertices that are closer to the site of the block than to any other site. This method return the site vertex of the block that contains the vertex, namely the site with the shortest path from any site to the vertex.

      Parameters:
      vertex - a vertex
      Returns:
      the site vertex with the shortest path from any site to the vertex, or null if the vertex can not be reached from any site