algorithm - 如何重新索引稀疏关联数组

Question

首先，这个问题与特定语言无关——我使用 Haxe 来针对多个平台——所以伪代码就足够了。

这是我的问题:我有一个 sparse Matrix这种形式的描述:

edges = 
[
1,1,2,1,3,1,4,1,
2,2,3,2,
3,3,4,3,5,3,
4,4,5,4,6,4,
5,5,6,5,7,5,25,5,27,5,28,5,29,5,30,5
];

这描述了边缘关联:

• 点 1 链接到点 1、2、3 和 4
• 点 2 链接到点 2 和 3
• 第 3 点与第 3、4 和 5 点相关联
• 第 4 点与第 4、5 和 6 点相关联
• 第 5 点与第 5、6、7、25、27、28、29 和 30 点相关联

现在我需要以 3D 形式呈现它，为此，我需要将数据“压缩”到一个没有“间隙”的索引缓冲区中。说上面的例子，我需要得到:

newEdges = 
[ 
1,2, 1, 3, 1, 4,
2,3,
3,4, 3,5,
4,5, 4,6,
5,6, 5,7, 5,8, 5,9, 5,10, 5,11, 5,12
]

因此，必须移除连接自身的边(边 1-1、2-2、3-3 等)(简单)。

由于点顺序并不重要(边 1-2 = 边 2-1)，我们还将删除重复的边(有点简单)。

现在棘手的部分是消除“差距”:因为 7 是最高的连续值，25 是紧随其后的值，所以 25 必须变成 8，27 必须变成 9，28 必须变成 10，依此类推。

现在我使用的是 BitmapData，其中我将所有值绘制为 XY 坐标。然后我递归地将此位图的非空垂直条纹(1 像素宽的矩形)彼此相邻复制到临时位图中。然后我对水平条纹执行相同操作，最后扫描我的位图并将像素的 X 和 Y 值存储为边缘 ID。

它有效!(至少它看起来有效 :))但是开销非常大，并且取决于输入矩阵，我可能无法生成位图(例如 flash 最大限制为 4092 像素，JS 不能很好地支持 copyPixels)。

所以问题是，如果没有位图和特定语言的方法，您将如何进行这种“间隙消除”？

希望这是足够明确的，感谢您的关注。

尼古拉斯

Answer 1

令E[m+1][m+1]为对应于edges的二维邻接矩阵，其中点索引的范围为[0. .m].

设 f[n] 是在 edges 中访问的 n 点的排序数组。通过创建 f[n] 数组，我们在 [0..m] 范围内的非连续点索引和 [0..n-1] 范围内的连续点索引之间创建了一个映射].

创建一个新的邻接矩阵G如下:

for i = 0..(n-1)
    for j = 0..(n-1)    // or, j = (i+1)..(n-1) for upper triangular portion
        G[i][j] = E[f[i]][f[j]]
    end
end

这只需要 O(n^2) 而不是 O(m^2) 的时间。

编辑:删除了 if 语句。如果 E 和 G 都初始化为全 0，则不需要。