Module org.jgrapht.core
Package org.jgrapht.alg.interfaces

Interface CentersLocationAlgorithm<V,E>

Type Parameters:
V - the graph vertex type
E - the graph edge type
All Known Implementing Classes:
CentersLocationAlgorithmBase, GonHeuristic
public interface CentersLocationAlgorithm<V,E>
An algorithm for solving the vertex $k$-center problem.

Center location problems are a class of optimization problems in graph theory and operations research that aims selecting optimal locations for facilities (centers) to minimize the distance or cost for serving a set of demand points or clients (vertices) in a graph.

Author:
Jose Alejandro Cornejo-Acosta

  • Method Summary

    Modifier and Type
    Method
    Description
    Map<V,V>
    getAssignment()
    Computes the assignment of vertices to their respective centers.
    Set<V>
    getCenters(Graph<V,E> graph, int k)
    Computes a set of centers.
    double
    getCoveringRadius()
    Obtains the covering radius of the solution.

  • Method Details

    • getCenters

      Set<V> getCenters(Graph<V,E> graph, int k)
      Computes a set of centers.
      Parameters:
      graph - the input graph.
      k - the number of centers to locate.
      Returns:
      a set of centes.

    • getAssignment

      Map<V,V> getAssignment()
      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 getCenters(org.jgrapht.Graph<V, E>, int) method has been called.
      Returns:
      a mapping from vertices to their assigned centers

    • getCoveringRadius

      double getCoveringRadius()
      Obtains the covering radius of the solution.
      Returns:
      the covering radius of the solution.