1

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

0 2
0 9
2 8
6 9

我想将边缘列表转换为压缩稀疏行（定义）格式。这意味着读取边缘列表并写入三个数组：Value（在我的情况下始终为“1”）、Column_Index 和 Row_Pointer。

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

问题

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

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

问题

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

4

2 回答 2

0

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

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

您还可以生成第二个边缘列表 where 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]是 i，然后继续NodesJI[q]。

我们还可以避免总是检查row_ind初始化，注意如果csr索引没有改变，那么该行是空的，对应的值可以是 -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 的存储空间。

于 2012-10-19T09:12:49.680 回答
0

您的数据采用所谓的三元组稀疏格式，其中您有明确的行列索引。你想做的是两件事：

  • 将三元组格式转换为 CRS
  • 由于某些条目可能丢失并且您想要一个无向图，因此您的最终矩阵将是 A = A+A' （转置）

为了跟进您的示例，final A 将同时包含(0,2)和(2,0)条目。

转换可以通过多种方式完成。查看一个非常完善的SuiteSparse 库，尤其是 cholmod_triplet.c 文件，它实现了您需要的功能。本质上，它是在行和列索引上使用两阶段桶排序执行的，同时删除重复项。该算法具有线性复杂性，如果您对处理大型数据集感兴趣，那就太好了。转置和许多其他有用的稀疏操作也可以使用该包完成。

于 2012-10-19T13:22:14.297 回答