6

我有一个完全无向图，其中节点表示平面上点上的点，边是点之间的近似欧几里得距离。我想将此图“嵌入”到二维空间中。也就是说，我想将每个顶点转换为 (x,y) 位置元组，以便对于任意两个两个顶点 v 和 w，边 (v,w) 的权重接近 dist(v,w)。

例如，如果我有一个带有节点 A、B、C 和 D 的图和带有权重 (A,B) 的边：20；(A,C): 22; (A,D): 26; (B, C): 30; (B, D): 20, (C, D): 19, 那么你可以分配点 A: (0,0); B: (10, 0); C: (0, 10); D: (10, 10)。显然这是不完美的，但它是一个合理的近似值。

我不在乎获得最好的解决方案，我只想在合理的时间内找到一个合理的解决方案。

（如果你想要这个问题的动机。我有一个物理系统，我对所有点对的距离进行嘈杂的测量。距离测量很嘈杂，但往往在真实值的两倍之内。我有做了所有这些测量，现在有一个包含数千个节点和数百万条边的图，并且想要将这些点放在一个平面上。）

4

2 回答 2

3

您可以根据需要调整基于力的图形绘制算法。

该算法试图G(V,E)通过将每个顶点V视为笛卡尔点并将每个边E视为线性弹簧来为无向图找到良好的布局。此外，全局计算顶点之间的成对排斥力（即库仑定律） - 这可以防止在笛卡尔空间中不相邻的顶点聚集G(V,E)。

在您的情况下，您可以将弹簧的平衡长度设置为等于您的边缘权重 - 这应该会给出一个布局，其中成对的欧几里德顶点距离接近您的边缘权重。

该算法基于每个顶点的力总和以伪时间步进方式更新初始分布（可能是随机的）。当达到近似稳态时，算法终止。一个简化的伪代码：

while(not converged)
    for i = vertices in V
        F(i) = sum of spring + repulsive forces on ith vertex
    endfor
    Update vertex positions based on force vector F 
    if (vertex positions not changing much)
        converged = true
    endif
endwhile

可以应用许多优化来降低算法的复杂性。例如，可以使用空间索引（例如四叉树）来允许有效计算“附近”顶点之间的近似斥力，而不是缓慢的全局计算。也可以使用多级图聚合技术来提高收敛性和最优性。

最后，请注意，有几个很好的图形绘制库可以实现该算法的优化版本 - 例如，您可能想查看Graphviz。

于 2013-01-15T00:50:06.920 回答
1

对于初学者，我想我会采用启发式搜索方法。

您实际上想找到一组点 p1,p2,...,p_n 来最小化函数：

f(X) = Sum (|dist(p_i,p_j) - weight(n_i,n_j)|) [for each i,j ]

该问题可以通过一些算法启发式地解决，包括爬山算法和遗传算法。

我个人喜欢爬山，方法如下：

best <- [(0,0),(0,0),...,(0,0)]
while there is still time:
    S <- random initialized vector of points
    flag <- true
    while (flag):
        flag <- false
        candidates <- next(S) (*)
        S <- X in candidates such that f(X) <= f(Y) for each X in candidates (**)
        if f(S) was improved:
            flag <- true
    if f(S) <= f(best):
        best <- S
return best

(*)next() 生成候选列表。例如，它可以利用有关函数梯度的信息（并且基本上衰减为类似于梯度下降的东西），或者采样一些随机“方向”并将它们作为候选（全部在多维向量中，其中每个点都是一个维度） ）。
(**)在这里，您基本上选择了“最佳”候选者，并将其存储在 S 中，因此您将在下一次迭代中继续使用它。

请注意，该算法是any-time，因此您必须给它更多的时间，预计它会变得更好。这种行为是通过起始点的随机初始化（可能会改变结束结果）以及通过随机选择候选点来实现的。

于 2013-01-14T22:46:23.043 回答