Как получить матрицу смежности из матрицы в C#

Question

полагая, у меня есть матрица, как

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

так что в этом случае матрица представляет:

0 являются проведён и -1 не Как могу ли я получить от него матрицу Adjacency?

Я знаю

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) 

так, что я делаю что-то вроде:

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

Матрица смежности является n по n матрица для графа с n узлами (см пример here), так как @harold высказал уже. Таким образом, вам необходимо сопоставить физические координаты узла в вашей сетке и номер узла, который находится между 0 и n-1.

Вот код, который находится по правому краю. Я просмотрел вывод в отладчике и проверил первые пару строк, которые он выглядел нормально.

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(); 
    } 
} 

Answer 2

Исходный код имеет проблему - матрицы adjacent и original не обычно одинаковый размер.

Но это близко, в некотором роде.

Код не проверял:

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 отображает 2D точку на "индекс узла". Это может потребоваться больше аргументов. Это может быть примерно так:

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

Есть и другие возможности, но это самые простые.