1

我正在寻找一种类似于 graphviz 的工具，它可以渲染图形，但这将允许我只限制每个节点的 x 坐标。然后，该工具将自动选择 y 坐标以使图形看起来整洁。

基本上，我想制定一个时间表。

语言/平台/渲染介质不是很重要。

4

1 回答 1

0

如果您想要一个看起来整洁的图表，那么力导向算法将是您最好的选择。最好的之一是 SFDP（由 AT&T 开发，包含在 graphviz 中），尽管我似乎找不到伪代码或简单的实现。我不认为有任何专门的算法。值得庆幸的是，编写自己的代码很容易。我将展示一些伪代码，大部分来自维基百科，但经过适当的一维修改。我假设您有n顶点，并且 x 位置的向量是x，下标为x.i。

set all vertex velocities to (0,0)
set all vertex positions to (x.i, random)
while (KE > epsilon)
    KE = 0
    for each vertex v
        force = (0,0)
        for each vertex u != v
            force = force + (0, coulomb(u, v).y)
            if u is incident to v
                force = force + (0, hooke(u, v).y)
        v.velocity = (v.velocity + timestep * force) * damping
        v.position = v.position + timestep * v.velocity
        KE = KE + |v.velocity| ^ 2

这里.y表示获得力的 y 分量。这确保了顶点位置的 x 分量永远不会改变您设置的位置。该参数由您设置，并且与您期望的（动能）epsilon相比应该很小 。KE此外，|v|表示向量的大小v（上述所有计算都是 2 向量，除了 KE）。请注意，我将所有节点的质量设置为 1，但您可以根据需要更改它。

Hooke和Coulomb函数计算节点之间的各自力；第一个顶点之间的距离是线性的，第二个是二次的，因此有保证的平衡。这些功能看起来像

def hooke(u, v)
    return -k * |u.position - v.position|

def coulomb(u, v)
    return C * |u.position - v.position|

大多数计算都是向量形式的。C 和 k 具有实际值，但要尝试获得所需的图形。这通常不是必需的，因为缩放因子会在两个维度上扩展或收缩整个图形，但是这里设置了 x 距离，因此要获得漂亮的图形，您必须稍微更改值.

于 2012-12-31T06:51:59.390 回答