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

Class 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 in order to augment an existing partial set of centers. See constructor GonHeuristic(Set).

    The runtime complexity is $O(k*|V|)$.

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

    Author:
    Jose Alejandro Cornejo-Acosta

    • Constructor Detail

      • GonHeuristic

        public GonHeuristic​(Random rng)
        Constructor. By default the first vertex is chosen randomly.
        Parameters:
        rng - random number generator.

      • GonHeuristic

        public GonHeuristic​(Set<V> initialCenters)
        Constructor Specifies a partial set of initial centers that will be augmented to form a set of k centers when #getCenters(java.util.Set) is called.
        Parameters:
        initialCenters - Initial set of centers.

    • Method Detail

      • 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.