Graphviz 的替代方案,为大图提供更好的自动节点放置?

软件推荐 图片 数据可视化 图表
2021-10-26 18:59:03

在过去,我使用 Graphviz 来绘制图形。这是一个很好的小图工具。

但不幸的是,对于大图,Graphviz 真的很烂:

  • 它总是越过显然可以在没有十字架的情况下绘制的边缘。
  • 它叠加不同的文本,使它们不可读。
  • 它没有可重用的样式(如 CSS),您需要在节点和边缘中一遍又一遍地重复相同的个性化设置。
  • 如果用户想,只是说,交换两个节点的位置。为此,经常需要大量破解源文件,可能会在此过程中破坏图形的不相关部分。
  • 很容易,为了在图形的一个孤立位置进行小的更改,Graphviz 在其他地方强制进行重大的重大更改,经常使试图说服它正确绘制它的工作时间无效。
  • 它在图表中浪费了大量空间,同时在某些地方非常拥挤。
  • 有时,一些边会形成非常曲折的路径来连接源节点和目标节点,具有奇怪的无用曲线和大量叠加的横向运行边。
  • 它具有雪崩效应。图中某处的细微修改可能会扰乱 Graphviz 启发式算法,从而导致完全不同的图。
  • 很多bug...

作为用户,我想要一些东西,我可以简单地:

  • 定义节点是什么,可能带有要应用的样式。
  • 说出边缘是什么,可能带有要应用的样式。

然后程序给出:

  • 具有最少可能交叉次数的图。
  • 非常对齐的节点很好。

我不想:

  • 只是因为该工具太愚蠢以至于看不到它可以交换两个特定节点以删除交叉点,因此在输入上添加了很多技巧。
  • 手动需要定位边和节点。
  • 获得雪崩效应。

那么,什么是 Graphviz 的好替代品呢?我真的希望它是免费的。

注意:我不太关心应该输入图形的格式,只要我可以保存和编辑带有图形描述的文件(无论这种描述的语言是什么)。所以,绝对没有必要仍然使用点语言或类似的东西(事实上,我很乐意完全丢​​弃我的点文件,因为那里的黑客比实际的图形描述要多得多)。

4个回答

很抱歉让您失望了。Graphviz 在很多方面可能会更好,但在这一点上,前景并不好,因为 AT&T 不像过去那样支持这项工作,而且一些作者(比如我)已经离开去寻找其他的工作。我们正在寻找想要接管它的人,所以请告诉我们。

我们也对yFiles印象深刻。

也可以试试Tom Sawyer 软件他们有很多工程人才,在先进的布局方法和交互工具方面做了很多工作。(您可能需要花费 $$,因为免费试用似乎已停止。)

该问题没有说明尝试了哪些特定的布局工具或选项,也没有说明“大型”网络有多大,因此尚不清楚该建议什么。

如果“大”意味着可能有数百个节点,请尝试neato -Goverlap=false(以避免节点文本标签重叠)并可能-Gmodel=subset尝试更好的聚类。(这些选项不是默认选项,因为在数据分析中,例如在生物信息学中,直接 MDS 嵌入可以更准确地呈现底层网络中的距离。)

如果“大”意味着数千个节点,可能是数千个,请使用-Goverlap=falsesfdp而不是再次使用。neato(子集距离模型在 sfdp 中不可用,因为在分层求解器中合并边时不清楚如何处理可变边长。)您可以在此处查看1054 节点图的一个很好的示例

对于断开连接的组件情况下的“浪费空间问题”,另请参见 pack 和 packmode 属性。此类问题的解决方案并不明显(基本上,您正在尝试以最佳方式打包不规则形状,带有额外的约束,有时在人们认为“大”的任何规模上,因此需要二次算法。)对于连通图,尝试-Goverlap 选项。

这些是建议。至于借口和解释……

有人所说的“雪崩效应”也称为相对于输入图中的(微小)变化的布局不稳定性。这是几乎所有批处理图布局程序和约束求解器的属性。所以你应该寻找像 D3 spring embedder layout 这样的交互式工具,Tim Dwyer 在微软的时候在这方面做了很多很棒的工作,所以也许有一天他们的 Graph Layout toolkit (AGL) 会采用他的交互式约束方法。只是一个观察,大多数研究人员和程序员并没有试图同时攻击规模、交互性和美学(选择上述任意 2 项......)

样式问题也是一个很好的问题,我们只是没有时间/精力来解决它,因为大多数图形都是自动生成的,因此您可以在一些预处理工具或脚本中应用样式。另外需要考虑的是,图不仅仅是静态解析树,读取图后,可以改变其样式表或应用了样式的对象的属性,然后必须将图写出来以尽可能保留原始结构的方式正确。并非不可克服,但这些都是必须仔细考虑的细节。

可以在 www.graphviz.org 的 Bug 和问题跟踪下报告错误。

具有平滑曲线的全局边缘路由 - 难题。请注意,其他一些工具的许多看起来很酷的布局都使用弯曲的边缘,但它们只是覆盖了其他所有阻碍的东西。我认为我们也将此功能添加到了 graphviz。此外,我认为有一篇 CHI 或 INFOVIS 论文显示,这种弯曲的边缘实际上比直线更难正确阅读。

过境点 - 一些局部优化可能是可能的。不确定使用的是什么工具。指出布局可能更好的具体示例很容易,但很难发明一个有效的解决方案,即“最少的交叉点”实际上不会使事情变得更糟。

请注意,我直接隶属于 Graphviz。

我的软件推荐是“ yEd ” - 一个免费的啤酒通用图形绘制应用程序,它非常努力地解决您遇到的问题。据我所知,该软件使用最好的免费版图算法实现。

现在到更详细的答案,它比“软件推荐”更适合 StackOverflow:

您尝试解决的问题是一个非常困难的问题(尤其是在计算困难的意义上),因此您不太可能找到能够同样解决所有问题的工具。有许多免费的解决方案(GraphViz 可能是最好的解决方案之一)和相当多的商业竞争对手。对于商业yFiles图形绘制库,有一个免费的(如啤酒)跨平台应用程序可用,您可以尝试。它可以从几种不同的格式导入数据,将样式映射应用于您的数据,并提供大量不同的布局算法。它被称为yEd,无需任何安装即可从此处在 Web 版本中运行. 桌面版本可以作为 java“webstart”应用程序直接从浏览器启动,也可以在安装适用于 Windows、Linux 和 Mac 的独立程序之一之后启动。

一些布局算法可能不应该用于非常大的图形(数万个元素),因为它们会执行很长时间或需要太多内存,但大多数时候至少有一种布局样式应该很适合您的数据。如果您需要针对 API 进行编程,则需要许可底层库(适用于 Java、.net、Javascript),这违反了您的“免费”要求,但这将使您对布局有更多的控制权。

免责声明:我为创建此(免费)产品的公司工作,但是在 Stack Exchange 上我不代表我的雇主。自 1990 年代后期以来,我将大部分学术和专业时间都花在了图形绘图软件上,我相信我对市场和可用软件(免费和商业)有非常深入的了解。可能还有其他可用的工具,我希望这个网站可以提供很好的选择——我当然不会否认。

要非常具体地回答问题的要求,因为其他两个答案在扩展方面做得很好:

你问的是不可能的。您需要一个程序,该程序提供“具有最少可能交叉数的图形。”,并且您特别要求该程序适用于大型图形。

然而,确定图的交叉数是一个NP-hard 问题(Garey 和 Johnson在 1983 年表明它是 NP-complete)。

因此,这样的程序将无法保证在合理的时间内找到具有最少可能交叉次数的图形,从而使程序无用。

这肯定会被视为“基于 GraphViz 的解决方案”,但如果您正在使用 GraphViz,您可能需要查看Gephi在处理大型图形时,它的功能要强大得多。