How to Get Adjacency matrix from a matrix in c#

Question

supposing I have a matrix like

0 -1  0  0
0  0 -1  0
0  0  0  0
0  0 -1 -1

so in this case The matrix represents:

0's are conected and -1 are not How can I get Adjacency matrix from it?

I know

h[i][j] = 0, if there is no direct link from i to j 
(i and j are not neighbors)
h[i][j] = 1, if there is a direct link from i to j 
(i and j are neighbors)

so I am doing something like:

Int32[,] original = new int[4, 4]
{
  {0, -1,  0,  0},
  {0,  0, -1,  0},
  {0,  0,  0,  0},
  {0,  0, -1, -1}
}

Int32[,] adjacent;
for (int i = 0; i < original.GetLength(0); i++){
    for (int j = 0; j < original.GetLength(1); j++) {
         //How to know if there is direct link from i to j 
         //if(){
         //   adjacent[i,j]=0;
         //}else{
         //   adjacent[i,j]=1;
         //}
    }
 }

Answer 1

The original code has a problem - the matrixes adjacent and original are not usually the same size.

But it's close, in a way.

Code not tested:

int size = original.GetLength(0) * original.GetLength(1);
int[,] adjacent = new int[size, size];
for (int i = 0; i < original.GetLength(0); i++) {
    for (int j = 0; j < original.GetLength(1); j++) {
        if (original[i, j] == 0) {
            // up/down
            if (j > 0 && original[i, j - 1] == 0) {
                adjacent[remap(i, j), remap(i, j - 1)] = 1;
                adjacent[remap(i, j - 1), remap(i, j)] = 1;
            }
            // left/right
            if (i > 0 && original[i - 1, j] == 0) {
                adjacent[remap(i, j), remap(i - 1, j)] = 1;
                adjacent[remap(i - 1, j), remap(i, j)] = 1;
            }
        }
    }
 }

remap maps a 2D point to a "node index". It may need more arguments. It could be something like:

int remap(int i, int j, int width)
{
    return width * i + j;
}

There are other possibilities, but this is the simplest.

Answer 2

The adjacency matrix is an n by n matrix for a graph with n nodes (see an example here), as @harold has stated already. So you need to map between the physical (i,j) coordinates of the node in your grid, and the node number which is between 0 and n-1.

Here is some code that is along the right lines. I have looked at the output in the debugger and checking the first couple of rows it looked ok.

class Program
{
    static void AddToAdjacencyMatrix(Int32[,] adjacency, Int32[,] original,
        Dictionary<Tuple<int, int>, int> coordinate2NodeNum,
        Tuple<int, int> fromCoord, int deltaX, int deltaY)
    {
        Tuple<int, int> toCoord = new Tuple<int, int>(
            fromCoord.Item1 + deltaX, fromCoord.Item2 + deltaY);
        try { // quick and dirty way of catching out of range coordinates
            if (original[toCoord.Item1,toCoord.Item2] == 0) {
                int fromNodeNum = coordinate2NodeNum[fromCoord];
                int toNodeNum = coordinate2NodeNum[toCoord];
                adjacency[fromNodeNum, toNodeNum] = 1;
                adjacency[toNodeNum, fromNodeNum] = 1;
            }
        }
        catch {
        }
    }

    static void Main(string[] args)
    {
        Int32[,] original = new int[4, 4]  
        {
          {0, -1,  0,  0},
          {0,  0, -1,  0},
          {0,  0,  0,  0},
          {0,  0, -1, -1}
        };

        // Adjacency matrix has column and row headings for each node in graph
        // Therefore we need to map between the node number in the adjacency matrix
        // (i.e. the column or row heading) and the physical grid coordinates
        Dictionary<int, Tuple<int, int>> nodeNum2Coordinate = new Dictionary<int, Tuple<int, int>>();
        Dictionary<Tuple<int, int>, int> coordinate2NodeNum = new Dictionary<Tuple<int, int>, int>();
        int nodeCount = 0;
        for (int i = 0; i < original.GetLength(0); i++){
            for (int j = 0; j < original.GetLength(1); j++) {
                if (original[i, j] == 0) {
                    Tuple<int, int> coord = new Tuple<int, int>(i,j);
                    nodeNum2Coordinate.Add(nodeCount, coord);
                    coordinate2NodeNum.Add(coord, nodeCount);
                    nodeCount++;
                }
            }
        }

        // Now create the adacency matrix
        Int32[,] adjacency = new int[nodeCount, nodeCount];
        for (int i = 0; i < original.GetLength(0); i++){
            for (int j = 0; j < original.GetLength(1); j++) {
                if (original[i, j] == 0) {
                    Tuple<int, int> fromCoord = new Tuple<int, int>(i,j);
                    // Check connections
                    AddToAdjacencyMatrix(adjacency, original, coordinate2NodeNum, fromCoord,
                        -1, 0); // UP
                    AddToAdjacencyMatrix(adjacency, original, coordinate2NodeNum, fromCoord,
                        +1, 0); // DOWN
                    AddToAdjacencyMatrix(adjacency, original, coordinate2NodeNum, fromCoord,
                        0, -1); // LEFT
                    AddToAdjacencyMatrix(adjacency, original, coordinate2NodeNum, fromCoord,
                        0, +1); // UP
                }
            }
        }
        Console.ReadLine();
    }
}