How to Create ArrayList of Neighbors to Coordinate Node in Undirected Graph?

Question

Given a 2d array matrix, the goal is to locate all adjacent coordinates, instantiate them as objects and add them to an ArrayList for later use. The issue I'm having is accounting for edge cases where the neighbors might be out of matrix bounds. With that, what is the best method to state the bounds of a 2d array in Java so that it maybe caught by a conditional statement?

Tried the following below. Unsure how to account for cases where one of the neighbors is outside of the matrix bounds (ex. a corner node with only two neighbors).


import java.util.ArrayList;

class Node{

    private int nodeX;
    private int nodeY;

    public Node(int enterX, int enterY){
        nodeX = enterX;
        nodeY = enterY;
    }



    public ArrayList<Node> getNeighbors(int[][] enterGraph){

        ArrayList<Node> adjacentNodes = new ArrayList<>();


        if(this.nodeX + 1 > /*Farthest value right in row*/){
             Node right = new Node(this.nodeX + 1, this.nodeY);
             adjacentNodes.add(right);
        }
        if(this.nodeX - 1 < /*Farthest value left in row*/){
             Node left = new Node(this.nodeX - 1, this.nodeY);
             adjacentNodes.add(left);
        }
        if(this.nodeY + 1 < /*Farthest value up in row*/){
             Node up = new Node(this.nodeX, this.nodeY + 1);
             adjacentNodes.add(up);
        }

        if(this.nodeY - 1 < /*Farthest value down in row*/){
             Node down = new Node(this.nodeX, this.nodeY - 1);
             adjacentNodes.add(down);
        }


        return adjacentNodes;
    }

}

Take for instance the following matrix:

0, 0, 0
7, 1, 0
0, 7, 0

The final ArrayList should output the following:

Current node = (1, 0), where value equals 7.

ArrayList of neighbors equals = {(0,0), (1,1), (2,0)}, where values equal 0, 1, 0 respectively.

Apologies. Fixed some elements for compilation purposes. A warning being, that this still will not compile, as there are comments in the conditional statements where I would like a bit of wisdom. As a novice, this is merely an attempt to get out my question as best as possible, with only a high-level implementation idea. Unsure of how to even make this function, yet alone make it cleanly coded. — , Sep 17 '19 at 03:57

nits.kk · Answer 1 · 2019-09-17T08:10:45.613

For a given (x,y) in a 2D matrix of size NxM , you need UP(x,y-1), DOWN(x,y+1),LEFT(x-1,y),RIGHT(x+1,y) neighbours.

A simple function to check the array bounds can be defined with below signature.

Any cell in the matrix is defined by its both the co ordinate, just one is not enough, so you need to check both the co ordinate of a neighbour to come to a conclusion that it is within the array bounds.

boolean isSafe(int x, int y, int N, int M)

isSafe will check if the x, y lies within the range of array bounds, check for both upper (N,M) and lower bounds(0). You can easily implement this function (in case any one of x or y is out of bounds return false. If none is out of bounds return true)

Now the for a given (x,y) Check the coordinate of a neighbour, like for UP its (x,y-1), using the function isSafe and if it returns true then add to the List else ignore it.

Also I suggest you to keep value in the class Node.

P.S : You can refer to the adjacency list as you are trying to get something (not exactly may be) very similar to the same

score 0 · Accepted Answer · answered Sep 17 '19 at 04:19

0

I suspect what you want to do is compare to the size of the array you've been passed:

if (nodeX > 0)
    adjacentNodes.add(new Node(nodeX - 1, nodeY));
if (nodeX < enterGraph.length - 1)
    adjacentNodes.add(new Node(nodeX + 1, nodeY));
if (nodeY > 0)
    adjacentNodes.add(new Node(nodeX, nodeY - 1));
if (nodeY < enterGraph[nodeX].length - 1)
    adjacentNodes.add(new Node(nodeX, nodeY + 1));

answered Sep 17 '19 at 04:19

sprinter

27,148
6
47
78

This appears to work, as when added to my example, it produces the appropriate quantity of adjacent nodes depending on the location of the examined node. Quick question, is there already a Stackoverflow question on converting an ArrayList of custom class objects to one of strings for printing purposes? – Sep 18 '19 at 03:06
Just create a `toString` method for your class and print the list - it will automatically convert each object to its string equivalent. – sprinter Sep 18 '19 at 09:08

How to Create ArrayList of Neighbors to Coordinate Node in Undirected Graph?

2 Answers2