Using DFS (depth first), find the density of blocks which density is over %X

Question

In my work (some matrix computation), i am stuck with a problem as below:

matrix (NxN):   
          xxxx------------------
          xxxx------------------
          ----xxx-x-------------
          ----xx--x-------------
          ---------x--x---------
          ---------xxxx---------
                   xxxx---------
            ......................

I have a 2D adj matrix has pattern of block daigonals (as shown above). Each block can be dense (100%) or sparse (0.01-5%). With these adj matrix and using graph search (DFS), how can I find the block size (begin_row, being_col, end_row, end_col) and also their corresponding density (mod(E)/mod(V))?

I am sure that there is an easy way to find the blocks and density. I am looking for any idea or pseudo-code, I would really appreciate for your time.

Answer 1

You can transverse the diagonal to map where each block starts and ends.
The transverse can be done by dfs or simple loop.
Then key is detecting a block end. With "full" blocks is is quiet simple as demonstrated in isCorner method. This method will have to be modified to account for holes.

    //test data
    public static int[][] intArray = {
        {1,  1,  0,  0,  0,  0,  0,  0,  0},
        {1,  1,  0,  0,  0,  0,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  0,  0,  0,  0,  1,  1,  1},
        {0,  0,  0,  0,  0,  0,  1,  1,  1},
        {0,  0,  0,  0,  0,  0,  1,  1,  1}
    };

    public static void main(String[] args) {

        mapBlock();
    }

    //traverse diagonal to find block start and block end
    private static void mapBlock() {
        //todo check that matrix is nxn

        int[] origin = {0,0}; //dfs start point
        //traverse diagonal
        for(int rowIndex =0; rowIndex < intArray.length ; rowIndex ++) {
            if(isCorner(rowIndex, rowIndex)) { //diagonal row and col index are equal
                int[] target = {rowIndex, rowIndex}; //dfs target
                block(origin, target);
                origin = new int[]{rowIndex+1, rowIndex+1};
            }
        }
    }

    //is intArray[row Index][column Index] a corner 
    private static boolean isCorner(int rowIndex, int colIndex) {

        //corner must be on diagonal
        if(rowIndex != colIndex ) {
            return false;
        }

        //if last row and col it is a corner
        if(((rowIndex+1) == intArray.length) && ((colIndex+1) == intArray.length))  {
            return true;
        }

        //if left and bottom neighbors are empty - it is a corner
        //todo if you blocks have holes this criteria needs to change
        if((intArray[rowIndex+1][colIndex] == 0) && (intArray[rowIndex][colIndex+1] == 0) ) {
            return true;
        }

        return false;
    }

    private static void block(int[] origin, int[] target) {

        System.out.println("block from " +Arrays.toString(origin)+
                " to "+Arrays.toString(target));
        //todo store sub array 
    }

Output:

block from [0, 0] to [1, 1]
block from [2, 2] to [5, 5]
block from [6, 6] to [8, 8]

(Test it online )