c# - C# で行列から隣接行列を取得する方法

Question

次のような行列があるとします

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

したがって、この場合、マトリックスは次を表します。

0 は接続され、-1 は接続されませんどうすれば隣接行列を取得できますか?

知っている

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

元のコードには問題があります。行列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;
            }
        }
    }
 }

remap2D ポイントを「ノード インデックス」にマップします。さらに引数が必要な場合があります。それは次のようなものかもしれません:

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

他にも可能性はありますが、これが最も簡単です。

Answer 2

隣接行列は、@harold が既に述べたように、ノードを含むグラフのnby行列です (こちらの例を参照)。したがって、グリッド内のノードの物理座標と、 と の間のノード番号をマッピングする必要があります。nn(i,j)0n-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();
    }
}