Package com.jgalgo.alg.shortestpath

Interface VoronoiAlgo

All Known Implementing Classes:

VoronoiAlgoAbstract, VoronoiAlgoDijkstra

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.

Author:

Barak Ugav

See Also:

ShortestPathSingleSource, IVertexPartition

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
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	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.

Returns:

a default implementation of VoronoiAlgo