SingleLink.java

Below is the syntax highlighted version of SingleLink.java from §9.4 Euclidean Graphs.

/******************************************************************************
 *  Compilation:  javac SingleLink.java
 *  Execution:    java Generator M N | java SingleLink 
 *  Depedencies:  Vector.java 
 *
 *  Johnson's algorithm
 *
 ******************************************************************************/

public class SingleLink { 
    public static double INFINITY = Double.POSITIVE_INFINITY;

    // for debugging only
    public static void show(String[] names, double[][] a, int[] mindist, int N) {
        for (int i = 0; i < N; i++) {
            StdOut.print(names[i] + " ");
            if (a[i][mindist[i]] == INFINITY) StdOut.print("( INF) : ");
            else StdOut.printf("(%4.0f) : ", a[i][mindist[i]]);
            for (int j = 0; j < N; j++) {
                if (a[i][j] == INFINITY) StdOut.print("  .  ");
                else StdOut.printf("%4.0f ", a[i][j]);
            }
            StdOut.println();
        }
        StdOut.println();
    }


    public static void main(String[] args) {
        int M = StdIn.readInt();    // number of experiments per gene
        int N = StdIn.readInt();    // number of genes

        // read in N vectors of dimension M
        Vector[] vectors = new Vector[N];
        String[] names   = new String[N];
        for (int i = 0; i < N; i++) {
            names[i] = StdIn.readString();
            double[] d = new double[M];
            for (int j = 0; j < M; j++)
                d[j] = StdIn.readDouble();
            vectors[i] = new Vector(d);
        }

        // initialize all-pairs proximity matrix
        // initialize min distance from i to any other point
        // can save space by using float or only storing lower triangular part
        // can save a little time by not computing square roots in distanceTo
        double[][] dist = new double[N][N];
        int[] mindist = new int[N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j) dist[i][j] = INFINITY;
                else        dist[i][j] = vectors[i].distanceTo(vectors[j]);
                if (dist[i][j] < dist[i][mindist[i]]) mindist[i] = j;
            }
        }
        StdOut.println("Done precomputing distances");



        if (N <= 10) show(names, dist, mindist, N);

        // N-1 single-link operations
        for (int s = 0; s < N-1; s++) {

            // find closest pair of vectors (i1, i2)
            int i1 = 0;
            for (int i = 0; i < N; i++)
                if (dist[i][mindist[i]] < dist[i1][mindist[i1]]) i1 = i;
            int i2 = mindist[i1];

            // change name of row i1 and print out connection
            String newname = "NODE" + s;
            StdOut.println(newname + " " + names[i1] + " " + names[i2] + " " + dist[i1][i2]);
            names[i1] = newname;

            // overwrite row i1 with minimum of entries in row i1 and i2
            for (int j = 0; j < N; j++)
                if (dist[i2][j] < dist[i1][j]) dist[i1][j] = dist[j][i1] = dist[i2][j];
            dist[i1][i1] = INFINITY;

            // infinity-out old row i2 and column i2 - do this before updating mindist
            for (int i = 0; i < N; i++) {
                dist[i2][i] = dist[i][i2] = INFINITY;
            }

            // update mindist
            for (int j = 0; j < N; j++) {
                if (mindist[j] == i2) mindist[j] = i1;
                if (dist[i1][j] < dist[i1][mindist[i1]]) mindist[i1] = j;
            }


            if (N <= 10) show(names, dist, mindist, N);
          
        }

    }
}