snarl

计算加权图的平面布局。

动机

存在大量的计算图布局的工具，例如备受推崇的 neato，交互式的 Gephi，以及如 igraph 和 networkx 这样的库，仅举几例。

为什么使用 Snarl

Snarl 的特点包括

• 处理密集的输入图。

  大多数（所有？）其他布局程序都假设输入图中所有的边都必须在布局中发挥作用。如果您的数据是密集的（例如，某些对象相似度的矩阵），则您必须首先构造一些稀疏边子集（例如，使用 K-最近邻）并将其传递给布局程序。

  相比之下，snarl 将乐于为您执行此任务。它将尝试从密集图中选择最重要的边，以便结果将是一个用于布局的“良好”的平面图。从密集图中提取最重平面子图的一般问题是 NP-hard，因此 snarl 使用启发式算法。此启发式算法还试图考虑图的 2D 布局。

  您仍然可以选择为 snarl 提供子图，如果只是为了性能考虑。然而，snarl 将提取平面子图这一事实意味着您在构建此类输入子图时需要更加宽松。

• 避免折叠。

  纯弹簧模型的缺点是它对边的交叉视而不见。举一个简单的例子，弹簧模型无法区分这种布局

     A--B
    /| /
   / |/
  C--D
  

  和这种布局

  A--B
  |\/
  |/\
  D--C
  

  实际上，它可能更喜欢后者，因为它更紧凑。然而，当涉及到向人类观察者传达图时，第二种布局是劣质的。一种技术上的评估方法是，在第二种布局中，节点 B 和 C 非常接近，但在图中它们相距很远。在理想的布局中，布局中的距离和图中的距离应该有很强的相关性。

  纯基于Spring的模型会根据节点（随机化）的起始位置愉快地生成这样的折叠。即使你有生成更好初始位置的方法，许多现有的工具（例如，neato）也不允许您将这些位置作为输入。

  折叠是密集图在传递给布局工具之前需要剪枝的主要原因。然而，即使您向这些工具传递完全平面的图，它们仍然会生成这样的折叠，因为它们唯一优化的只是弹簧能量，而不是边交叉。

  相比之下，snarl将从输入图中提取一个平面子图，这样二维布局将不会包含任何交叉边和折叠。

  您可以选择是否在弹簧模型中包含额外的（交叉）边，以及（独立地）是否在最终图中显示它们。对于密集的输入图，您通常应该在这两个步骤中都仅使用平面子图。如果您的图已经稀疏（但不是完全平面），包含这些边可能更有意义。

• 它既可用作可执行程序，也可用作模块化库。

  该程序允许在数据上简单应用完整管道。库允许构建替代管道，跳过步骤和/或用替代实现替换它们。

为什么不用Snarl

首先，snarl非常新，没有现有工具的成熟度。（欢迎提交错误报告和拉取请求！:-)

其次，让snarl自动从您的数据中提取平面子图可能不是您想要的事情。尽管snarl在应用其弹簧模型时可以利用额外的交叉边，但这并不是它设计或优化的目标。如果您还打算显示这些边，那么snarl可能不会比现有的成熟工具有优势。

安装

要安装

cargo install snarl

运行

待办事项。

输入格式

待办事项。

输出格式

待办事项。

链接

待办事项。

许可

snarl在GNU通用公共许可证（版本3.0）下分发。有关详细信息，请参阅LICENSE。