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:
    Path

    • Method Summary

      All Methods Instance Methods Abstract Methods 
      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 Detail

      • 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 block is the unreachable block