将边缘列表转换为 C 中的压缩稀疏行

Question

我有一个包含数百万条边的无向边列表。 10x10 稀疏邻接矩阵的无向边列表的简化示例:

0 2
0 9
2 8
6 9

我想将边列表转换为压缩稀疏行 (definition) 格式。这意味着读取边缘列表并写入三个数组:Value(在我的例子中始终为“1”)、Column_Index 和 Row_Pointer。

阅读示例边缘列表，我可以轻松地重建第 0 行:它在第 2 列和第 9 列中有一个“1”。然后，第一行没有非零条目。

问题

对于第 2 行，因为边缘是无向的，所以我假设在第 0 列和第 8 列中有一个“1”。但是列表中不存在“2 0”条目。我想此信息已编码在“0 2”条目中。

我可以读取部分构造的压缩稀疏行数组以查看“2 0”条目是否存在，但对于包含数百万条目的大型边缘列表，这不起作用。

问题

我该如何解决这个问题？还是我的方法不对？

Answer 1

您可以扫描边缘列表，交换索引，以便对于每个 (i, j) i < j 总是正确的.您在 O(N) 中执行此操作。

您还需要一个排序的边列表，这是 O(N log N)。获得排序后的边列表后，您可以将其存储为 Symmetric-CSR 格式。读取单元格时 (y,x) , 如果 y > x然后你交换y和 x .然后你读row_pointer[y]和 row_pointer[y+1] ，让他们成为Pa和 Pb , 然后开始扫描 CSR[i]我在 Pa 之间和 Pb ;如果 x 退出>= CSR[i] (找到或不找到取决于 if = 或 >)，或者如果 i == Pb (未找到)。

您还可以生成第二个边缘列表，其中 j > i , 也对其进行排序。此时，可以同时扫描两条边，生成不需要对称的CSR列表。

j0 = j1 = N+1
# i-th row:
    # we are scanning NodesIJ[ij] and NodesJI[ji].
    If NodesIJ[ij][0] == i
        j0 = NodesIJ[ij][1]
    If NodesJI[ji][0] == i
        j1 = NodesIJ[ji][1]
    if (j0 < j1)
        j = j0
        j0 = N+1
        ij++
    else
        if (j1 == N+1)
           # Nothing more on this row, and j0 and j1 are both N+1.
           i++;
           continue
        j = j1
        j1 = N+1
        ji++
    # We may now store (i,j) in CSR
    if (-1 == row_ind[i])
        row_ind[i]     = csr;
    col_ind[csr++] = j

上面的算法可以改进观察到对于任何给定的 i , 如果存在 p和 q这样 NodesIJ[p] = i和 NodesJI[q] = i , 它永远是 NodesIJ[p][1] > NodesJI[q][1]因为前一个列表描述了右上角的三角形，而后者描述了左下角的三角形。所以我们可以扫描 NodesJI 直到 NodesJI[p][0]是我，然后继续 NodesJI[q] .

我们也可以避免总是检查 row_ind初始化注意如果 csr index 不变，则该行为空，相应的值可以是 -1(或 N+1，或我们想要的任何“无效”值)，否则它必须是 csr 的先前值.

    scsr = csr;
    while NodesIJ[ij][0] == i
        col_ind[csr++] = NodesIJ[ij++][1]
    while NodesJI[ji][0] == i
        col_ind[csr++] = NodesJI[ji++][1]
    row_ind[i++] = (csr == scsr) ? -1 : scsr;

上面的运行复杂度为 O(N log N)。

另一种方法是分配矩阵，将边列表解码为矩阵并将其解析为 CSR。这是 O(N)，但可能需要太多内存；对于 N 的列表大小，您最多可能有 N^2(或 (N/a)^2，a 是平均连接数)个单元格。数百万条边的列表可能很容易需要数十 GB 的存储空间。