Convert 2d array into a graph

How I convert a 2 dimensional array to a graph. Where as every element of array connect with their neighbor (neighbor is up,down,right and left).

Suppose a 2x2 Array is :

[
  [A, B]
  [C, D]
]

The graph will be like that :

The adjacency matrix of the graph is like that :

	A	B	C	D
A	0	1	1	0
B	1	0	0	1
C	1	0	0	1
D	0	1	1	0

The adjacency list of the graph is like that :

A -> B,C
B -> A,D
C -> A,D
D -> B,C

What algorithm will be needed for this ?

I just try 2D array convert to graph in JS.

I have class named vertex :

class Vertex {
  constructor(value) {
    this.value = value;
    this.neighbors = [];
  }

  /**
   *
   * @param {Vertex} v
   */
  addNeighborsVertex(v) {
    this.neighbors.push(v);
  }
}

For example a 2D array :

let arr = [
    ["A","B"],
    ["C","D"]
]

A function which can take 2d array and convert to graph vertexes and return list of vertex. Each vertex contain arr value and their neighbor. Also neighbor list contain instance of Vertex. For example, Vertex for element "A" look like that:

{
    value : "A",
    neighbors : [
        instanceOfVertexB,
        instanceOfVertexC
    ]
}

No duplicate allowed. "A" and "D" has same neighbors which is "B". In that case both Vertex "A" and Vertex "D" hold same instance of Vertex "B".

How I can do that in js ?

Solution

As you said in the comment you don't want full code, I won't provide full code but just an idea for a simple approach how this could be done

create a allvertices: Map<string, Vertex> for storing all existing vertexes
iterate over the whole input array

For each vertex while iterating:

get the current vertex from the map.
```
let v = allvertices.get(vertexname);
```
this will either return the vertex if it is already contained in the map or undefined if not.
if v is undefined, create a v = new Vertex(vertexname) and add it to the map
```
allvertices.set(vertexname, v);
```
get all let neighbours = [arr[row-1][col],arr[row+1][col],arr[row][col-1],arr[row][col+1]] of the current vertex. You don't have to care for out of bound indexes in JS. Accessing a non-existing index of an array will not throw an Error, but just return undefined

For each neighbour in the neighbours array which isn't undefined:

check if it already exists in the allvertices map. If not create it and add it to allvertices (like above)
add it to the neighbour list of vertex v
```
v.addNeighbour(neighbour);
```

This way you will create exactly one Vertex for each entry of your input array and also the refrences will always go to the same node, ie you won't have duplicates, as requested ...

Another even simpler approach, which doesn't need an extra map (but two iterations of the input array)

iterate your arr once, and for each vertex replace the string you currently have in your array with an instance of the Vertex class
```
arr[row][col] = new Vertex(arr[row][col]);
```

iterate your arr a second time, and add all neighbours to the current vertex

let neighbours = [arr[row-1][col],arr[row+1][col],arr[row][col-1],arr[row][col+1]]
for (let n of neighbours) {
  if (n !== undefined) {
    arr[row][col].addNeighbour(n);
  }
}

Instead of creating a neighbours array, you could of course also do the respective checks if a neighbour is defined and add it then

if (arr[row-1][col]) arr[row][col].addNeighbour(arr[row-1][col]);
if (arr[row+1][col]) arr[row][col].addNeighbour(arr[row+1][col]);
...

Or you could of course also do this in one iteration only.

while iterating the array, check if the current element is a string or a Vertex. If it's a string replace it with a Vertex
```
if (typeof arr[row][col] === "string")
  arr[row][col] = new Vertex(arr[row][col]);
```
Then do the same for the neighbours
```
if (typeof arr[row+1][col] === "string")
  arr[row+1][col] = new Vertex(arr[row+1][col]);
if (typeof arr[row-1][col] === "string")
  arr[row-1][col] = new Vertex(arr[row-1][col]);
...
```
Again, you don't need to care for out-of-bound indexes here, because typeof undefined === "undefined" thus, the above conditions will evaluate to false and thus, nothing will be done if for instance row+1 is out of bounds.
And add the neighbours to the current vertex (like above)