Efficient way of linking grid tiles while creating distinct edges in Java

1
votes

There is a grid.

static Double [][] myTiles = new Double[row][column];

The goal is to connect each tile with an adjacent tile. Compare a value between the pair, construct a link between tiles to create the minimum spanning tree for a given grid.

Below is my initial approach to this issue:

Nine ( 9 ) groups of tiles are identified.

This is a picture of a grid of cells that are separated into nine distinct areas.

These groups have the same logic and the same availability of adjacent squares.

For each cell in my grid I decided to check a cell above, below, to the left and to the right. Certain cells cannot perform all checks when located on an edge of the grid. Below is the movement representation for each type of a tile.

A grid with the move availability for each tile.

My current solution is a nested for-loop with the below if-else statements:

            if ( row == 0 && column == 0)   {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));     }
            
            else if ( row == 0 && ( column > 0 && column < myTiles.length ) )   {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( row == 0 && column == myTiles.length )    {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( ( row > 0 && row < myTilese[row].length ) && column == 0 )    {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));    }
            
            else if ( row == myTilese[row].length && column == 0 )  {
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));    }
            
            else if ( row == myTilese[row].length && ( column > 0 && column < myTiles.length ) )    {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( row == myTilese[row].length &&  column == myTiles.length )    {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( ( row > 0 &&  row < myTilese[row].length ) && column == myTiles.length )  {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));}
            
            else    {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));}

The above logic creates at least two links and at most four. That's a lot of diplicates to sort when it comes to building a minimum spanning tree.

Is there an eloquent way of representing the above if-else block?

2
javamultidimensional-arraygridrow
You're using condition && a lot. I would use nested if-statements to group conditions together. – NomadMaker
It puts similar bits of code together. It makes it more obvious which bits of code could be replaced with new methods. However, there is not hard and fast rule for this. You asked for recommendations for more eloquent code, and I gave you one. Google on the net if you want more information on this. – NomadMaker

2 Answers

2
votes

This is much simpler:

if(row > 0) {
    // north
}
if(row < height) {
    // south
}
if(column > 0) {
    // west
}
if(column < width) {
    // east
}

Obviously this assumes you have at least a 2x2 grid.

I think you were over-thinking your implementation, however the code you posted could be easily refactored to make a good test-case.

0
votes

The most efficient way is to limit amount of links created per tile.

To make the logic produce less duplicates it is helpfull to escape the nesting-loops solution, and instead implement two separate for loops.

First step: Iterate through each tile, of each row column by column and make one link east or left until the edge is detected. When the edge is detected, skip the pointer one row down.

The second step: Iterate through each tile, of each column row by row and make one link south or down until the edge is detected. When the edge is detected, skip the pointer one column right.

A divided grid with traces of links connecting rows and columns.

This logic covers all the tiles, prevents IndexOutOfBoundsChecks, and reduces amount of duplicate links created.

        for ( tileColumn = 0; tileColumn < 74; tileColumn ++ )  {
            myEdge = new GraphEdge<String>();
            
            mySortingQueue.offer(createEdgeEast(myEdge, myTiles, tileRow, tileColumn));
            
            if ( tileColumn == 73 && tileRow < 34 ) {   
                tileColumn = 0;
                tileRow++;  }
        }   /*  End of the column for loop  */
        
        tileRow = ZERO;
        tileColumn = ZERO;
        
        for ( tileRow = 0; tileRow < 34; tileRow++ )    {
            myEdge = new GraphEdge<String>();
            mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, tileRow, tileColumn));
            
            if ( tileRow == 33 && tileColumn < 74)  {   
                tileRow = 0;
                tileColumn++;   }
        }   // End of the row for loop