java arrays algorithm graph-theory adjacency-matrix

Create adjacency matrix from char[][] array provided rules

I want to change a char[][] array (lets call it cA) into an adjacency matrix. An adjacency matrix has columns and rows equal to the number of elements in an array, and each vertex in the adjacency matrix is either true or false depending if the elements in the initial array are adjacent. I want to bend the rules a little and also constrain an adjacency matrix vertex to true iff the elements are adjacent and one of the elements is not a specific value.

Here's what cA array looks like:

z y z
z z z
z y y

The adjacency matrix (lets call it aM) for the cA array will be an int array of size [3*3][3*3]. The conditions for aM(i,j) to be true are that the elements i and j in cA array must be adjacent, but neither i or j can be "y".

Lets number the cA array elements 1 through 9.

1 2 3
4 5 6
7 8 9

aM can be described by doing the below operations:

aM(1,1) //false, no self-adjacency
aM(1,2) //false, 2 is a "y"
aM(1,3) //false, 1 is not adjacent to 3
aM(1,4) //true, 1 is adjacent to 4, neither are "y"
aM(1,5) //false, 1 is not adjacent to 5
aM(1,6) //false, 1 is not adjacent to 6
aM(1,7) through aM(1,9) //false, there is no adjacency between 1 and 7, 8, or 9
aM(2,1) through aM(2,9) //false, 2 is a "y"
...

Hopefully you get the idea. From the above, the adjacency matrix for cA is as below:

   1 2 3 4 5 6 7 8 9 (i)
 1 0 0 0 1 0 0 0 0 0
 2 0 0 0 0 0 0 0 0 0
 3 0 0 0 0 0 1 0 0 0
 4 1 0 0 0 1 0 1 0 0
 5 0 0 0 1 0 1 0 0 0
 6 0 0 1 0 1 0 0 0 0
 7 0 0 0 1 0 0 0 0 0
 8 0 0 0 0 0 0 0 0 0
 9 0 0 0 0 0 0 0 0 0
(j)

The rule being aM(i,j) == 1 iff i != j, i != "y" && j != "y", and both i and j are adjacent to each other.

I'm having difficulty concocting an algorithm to create an adjacency matrix provided a char[][] array. I've defined the rules, but finding constraints for iteration is problematic.

Solution

Try this:

static void set(boolean[][] aM, int cols, int row0, int col0, int row1, int col1) {
    int index0 = row0 * cols + col0;
    int index1 = row1 * cols + col1;
    aM[index0][index1] = aM[index1][index0] = true;
}

static boolean[][] adjacencyMatrix(char[][] cA) {
    int rows = cA.length;
    int cols = cA[0].length;
    boolean[][] aM = new boolean[rows * cols][rows * cols];
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (cA[i][j] == 'y')
                continue;
            if (i + 1 < rows && cA[i + 1][j] != 'y')
                set(aM, cols, i, j, i + 1, j);
            if (j + 1 < cols && cA[i][j + 1] != 'y')
                set(aM, cols, i, j, i, j + 1);
        }
    }
    return aM;
}

public static void main(String[] args) {
    char[][] cA = {
        {'z', 'y', 'z'},
        {'z', 'z', 'z'},
        {'z', 'y', 'y'},
    };
    boolean[][] aM = adjacencyMatrix(cA);
    for (boolean[] row : aM) {
        for (boolean cell : row)
            System.out.print(cell ? "1" : "0");
        System.out.println();
    }
}

The result is: