Package com.jgalgo.alg

Interface VoronoiAlgo

public interface VoronoiAlgo

Voronoi cells algorithm.

Given a graph \(G=(V,E)\) and a set of sites \(S \subseteq V\), the Voronoi cells of \(S\) are the sets of vertices that are closer to a site than to any other site. The Voronoi cells are a partition of the graph vertices, namely each vertex is assigned to exactly one site.

The distances and paths are directed 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().

If there are some vertices that are unreachable from any sites, the partition will contain an addition block with index siteNumber+1 that contains all these vertices.

Use newInstance() to get a default implementation of this interface. A builder obtained via newBuilder() may support different options to obtain different implementations.

Author:

Barak Ugav

See Also:

ShortestPathSingleSource, IVertexPartition

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	VoronoiAlgo.Builder	A builder for VoronoiAlgo algorithms.
static interface	VoronoiAlgo.IResult	A result object of VoronoiAlgo computation for IntGraph.
static interface	VoronoiAlgo.Result<V,E>	A result object of VoronoiAlgo computation.

Method Summary

Modifier and Type	Method	Description
<V,E> VoronoiAlgo.Result<V,E>	computeVoronoiCells(Graph<V,E> g, Collection<V> sites, WeightFunction<E> w)	Compute the Voronoi cells of a graph with respect to a set of sites and an edge weight function.
static VoronoiAlgo.Builder	newBuilder()	Create a new Voronoi cells algorithm builder.
static VoronoiAlgo	newInstance()	Create a new Voronoi cells algorithm object.

Method Detail

computeVoronoiCells

<V,E> VoronoiAlgo.Result<V,E> computeVoronoiCells(Graph<V,E> g,
                                                              Collection<V> sites,
                                                              WeightFunction<E> w)

Compute the Voronoi cells of a graph with respect to a set of sites and an edge weight function.

If g is an IntGraph, a VoronoiAlgo.IResult object will be returned. In that case, its better to pass a IntCollection as sites and IWeightFunction as w to avoid boxing/unboxing.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

sites - a set of sites

w - an edge weight function

Returns:

the Voronoi cells of the sites

newInstance

static VoronoiAlgo newInstance()

Create a new Voronoi cells algorithm object.

This is the recommended way to instantiate a new VoronoiAlgo object. The VoronoiAlgo.Builder might support different options to obtain different implementations.

Returns:

a default implementation of VoronoiAlgo

newBuilder

static VoronoiAlgo.Builder newBuilder()

Create a new Voronoi cells algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build VoronoiAlgo objects