Module org.jgrapht.core
Package org.jgrapht.alg.centers

Class GonHeuristic<V,E>

java.lang.Object
org.jgrapht.alg.centers.CentersLocationAlgorithmBase<V,E>
org.jgrapht.alg.centers.GonHeuristic<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
CentersLocationAlgorithm<V,E>
public class GonHeuristic<V,E> extends CentersLocationAlgorithmBase<V,E>
The Gon heuristic algorithm for the vertex $k$-center problem.

The vertex $k$-center problem is an NP-hard combinatorial optimization problem that receives a complete edge-weighted undirected graph $G = (V, E, w)$, and a positive integer $k$. The goal is to find a subset $C$ of $V$ such that $|C| = k$ and the maximum distance from any vertex in $V$ to the nearest vertex in $C$ is minimized. $C$ is called the set of centers. The vertex $k$-center problem has applications in clustering and facility location.

The Gon heuristic is a classic heuristic approximation algorithm for the vertex $k$-center problem. It works in a straightforward way. First, a vertex from the input graph is chosen randomly and added to the set of centers $C$. Then, iteratively, the farthest vertex from $V$ to $C$ is chosen and added to $C$. This process is repeated until $|C| = k$. This algorithm provides a guarantee to compute solutions for the vertex $k$-center problem no more than 2-times optimum. According to the literature, this is the best approximation factor (under $P \neq NP$). The implementation chooses the first vertex randomly. Alternatively, an existing set of centers $C$ with fewer than $k$ centers can be provided to be augmented. In this implementation, ties are broken by choosing the vertex with the lowest index.

The description of this algorithm can be consulted on:

T. F. Gonzalez Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 1985, 38, 293-306.

J. Garcia-Diaz, R. Menchaca-Mendez, R. Menchaca-Mendez, S. Pomares Hernández, J. C. Pérez-Sansalvador and N. Lakouari, "Approximation Algorithms for the Vertex K-Center Problem: Survey and Experimental Evaluation," in IEEE Access, vol. 7, pp. 109228-109245, 2019, doi: 10.1109/ACCESS.2019.2933875.

This implementation can also be used to augment an existing partial set of centers. See constructor GonHeuristic(Set).

The runtime complexity of the Gon algorithm is $O(k\cdot |V|)$.

This algorithm requires that the graph is complete, undirected, and edge-weighted.

Author:
Jose Alejandro Cornejo-Acosta

  • Constructor Details

    • GonHeuristic

      public GonHeuristic(Random rng)
      By default the first center will be chosen randomly.
      Parameters:
      rng - random number generator.

    • GonHeuristic

      public GonHeuristic(Set<V> initialCenters)
      Specifies a partial set of initial centers that will be augmented to form a set of $k$ centers when getCenters(org.jgrapht.Graph<V, E>, int) is called.
      Parameters:
      initialCenters - Initial set of centers.

  • Method Details

    • getCenters

      public Set<V> getCenters(Graph<V,E> graph, int k)
      Computes the set of $k$ centers by using the Gon heuristic.
      Parameters:
      graph - the input graph.
      k - the number of centers to locate.
      Returns:
      a set of centers.
      Throws:
      IllegalArgumentException - if the graph is not undirected.
      IllegalArgumentException - if the graph is not complete.
      IllegalArgumentException - if the graph contains no vertices.

    • getCoveringRadius

      public double getCoveringRadius()
      Description copied from interface: CentersLocationAlgorithm
      Obtains the covering radius of the solution.
      Returns:
      the covering radius of the solution.

    • getAssignment

      public Map<V,V> getAssignment()
      Description copied from interface: CentersLocationAlgorithm
      Computes the assignment of vertices to their respective centers. This method computes and returns the mapping function $f:V\setminus C \rightarrow C$. Each key represents a vertex in the graph, and the corresponding value represents the center to which the vertex is assigned. The mapping reflects the result of any center location algorithm after the CentersLocationAlgorithm.getCenters(org.jgrapht.Graph<V, E>, int) method has been called.
      Returns:
      a mapping from vertices to their assigned centers