Graphviz:如何插入两个新的链接节点并最小化边缘交叉？

Question

我有以下图表 :

如您所见,有两个自然集群.我想找出一种方法将这些聚类分成两个图.

当然,关键的一步是计算正确的分裂.我想插入两个节点n1和n2,将它们连接起来e(n1,n2),然后移动它们,最大限度地减少边缘交叉的数量(当然,将所有节点/边缘精确地固定在它们所在的位置).

谁能在这里提供任何帮助？我不认为graphviz有任何能让我这样做的东西.

Answer 1

我认为您在这里混合了两项不同的任务：一项是图表分析，另一项是图表的可视化。

Graphviz，顾名思义，是一个图形可视化工具。可视化可以采取多种形式，通常试图通过使连接的节点彼此靠近来“使其看起来更好”，从而减少视觉边缘长度。人们可以利用某种弹簧或重力模型来计算所有节点的最佳位置。其他选项包括圆形或外壳布局。

某种可视化不应成为图表分析的基础。图形属性（例如平均最短路径长度或聚类系数）独立于任何可视化。

你说你想“最小化边缘交叉的数量”。边交叉的数量是可视化的属性，而不是图表的属性！每次让 graphviz 计算布局时，即使图形未更改，它也可能会发生变化。谁说 2d 是图形的唯一可能表示形式？仅添加一维，就不会有任何边缘交叉。

我建议集中精力进行图形分析。不知道你是否了解NetworkX。他们有数十种算法来分析您的图表。也许 您对聚类和派系部分感兴趣。