Module org.maxicp
Package org.maxicp.util.algo

Class DistanceMatrix

java.lang.Object
org.maxicp.util.algo.DistanceMatrix
public class DistanceMatrix extends Object

  • Constructor Summary

    Constructors
    Constructor
    Description
    DistanceMatrix()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    static void
    checkTriangularInequality(int[][] dist)
    Checks whether a distance matrix respects the triangular inequality.
    static void
    enforceTriangularInequality(int[][] distance)
    Enforces the triangular inequality on the given distance matrix using the Bellman-Ford algorithm.
    static int[][]
    extendMatrixAtEnd(int[][] matrix, List<Integer> duplication)
    Extend a matrix, adding new rows and columns corresponding to other entries already present in the matrix.
    static int[][]
    randomDistanceMatrix(int nNodes)
    Generate a random distance matrix where the triangular inequality is enforced
    static int[][]
    randomDistanceMatrix(int nNodes, int bound)
    Generate a random distance matrix where the triangular inequality is enforced
    static int[][]
    randomDistanceMatrix(int nNodes, int bound, int seed)
    Generate a random distance matrix where the triangular inequality is enforced

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • DistanceMatrix

      public DistanceMatrix()

  • Method Details

    • enforceTriangularInequality

      public static void enforceTriangularInequality(int[][] distance)
      Enforces the triangular inequality on the given distance matrix using the Bellman-Ford algorithm. The shortest paths are computed between all pairs of nodes and the distance matrix is updated accordingly.
      Parameters:
      distance - a distance matrix

    • checkTriangularInequality

      public static void checkTriangularInequality(int[][] dist)
      Checks whether a distance matrix respects the triangular inequality. Prints a warning message on stderr if the triangular inequality is not enforced
      Parameters:
      dist - distance matrix

    • extendMatrixAtEnd

      public static int[][] extendMatrixAtEnd(int[][] matrix, List<Integer> duplication)
      Extend a matrix, adding new rows and columns corresponding to other entries already present in the matrix. This is typically done for extending a distance matrix if node are duplicated

      Example: - matrix = {{0, 1}, {2, 3}} - duplication = [0] - result = row 2 and column 2 added, corresponding to node 0: {{0, 1, 0}, {2, 3, 2}, {0, 1, 0}}

      Parameters:
      matrix - matrix that must be extended
      duplication - one element per new row and column to add, telling
      Returns:

    • randomDistanceMatrix

      public static int[][] randomDistanceMatrix(int nNodes)
      Generate a random distance matrix where the triangular inequality is enforced
      Parameters:
      nNodes - number of rows and columns in the distance matrix
      Returns:
      distance matrix of nNodes rows and columns

    • randomDistanceMatrix

      public static int[][] randomDistanceMatrix(int nNodes, int bound)
      Generate a random distance matrix where the triangular inequality is enforced
      Parameters:
      nNodes - number of rows and columns in the distance matrix
      bound - for the generation, points will be considered as lying on a bound X bound square. The larger the value of bound, the larger will the distances be
      Returns:
      distance matrix of nNodes rows and columns

    • randomDistanceMatrix

      public static int[][] randomDistanceMatrix(int nNodes, int bound, int seed)
      Generate a random distance matrix where the triangular inequality is enforced
      Parameters:
      nNodes - number of rows and columns in the distance matrix
      bound - for the generation, points will be considered as lying on a bound X bound square. The larger the value of bound, the larger will the distances be
      seed - seed used for random number generation
      Returns:
      distance matrix of nNodes rows and columns