在C中将edgelist转换为压缩稀疏行

Question

我有一个包含数百万条边的无向边列表。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”条目是否存在，但对于包含数百万条目的大型edgelist来说，这是行不通的。

问题

我该怎么解决这个问题？还是我的做法错了？

Answer 1

您可以扫描边缘列表，交换索引，这样对于每个(i, j)，i < j总是正确的。这是你在O(N)中做的。

您还需要一个排序的边缘列表，这是O(N log )。一旦您有排序的边缘列表，您可以存储它的对称-CSR格式。读取单元格(y,x)时，如果y > x，则交换y和x。然后读取row_pointer[y]和row_pointer[y+1]，让它们是Pa和Pb，并开始扫描Pa和Pb之间的i；退出if x >= CSR[i] (找到与否取决于if =或>)，或者如果i == Pb (未找到)。

您还可以在其中生成第二个边缘列表，并对其进行排序。此时，您可以同时扫描两个边，并生成不需要对称的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，即连接的平均数量)单元格。数以百万计的边缘列表可能很容易就需要数十of的存储空间。

Answer 2

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

• 将三重奏格式转换为CRS格式
• 由于有些条目可能会丢失，并且您需要一个无方向图，所以最终的矩阵将是A= A+A‘(转置)。

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

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