类图-最佳节点定位

Question

我试图使用d3.js和d3.dag构建一个类关系图模型查看器

这个查看器最关键的部分是它应该能够最优地定位节点，这样我们就不会有链路交叉(只要有可能)，并且应该能够清楚地看到与什么相关的内容。

我们知道：

• 每个节点的宽度
• 每个节点的高度
• 链路起始坐标
• 链路结束坐标
• 连接所有角坐标

我们希望：

• 来查看连接的结束(可以手动实现移动节点)。
• 以最小化交叉链接(如果可能的话)

我需要的是理论上的。

是否有任何已知的算法可以解决上述问题(语言不重要，我只需要理论参考)

举例如下

• 目前的情况是什么
• 我一个人能做什么？
• 什么才是完美的

示例1.

电流

​

​

可达

​

​

完美

​

​

示例2.

电流

​

​

可达

​

​

完美

​

​

示例3.

电流

​

​

可实现和完善的

​

​

示例4.

电流

​

​

可达

​

​

完美

​

​

示例5.

电流

​

​

可达

​

​

完美

​

​

示例6.

电流

​

​

完美

​

​

更新

在这种情况下，传统的(节点到节点链接)交叉已经最小化(多亏了d3-dag)。问题是，我们没有唯一的节点到节点的关系，我们还有一个节点对行的关系，在这种情况下，d3-dag会失败。

Answer 1

我使用d3-dag对节点进行拓扑排序，然后重新定位它们垂直，顶部如果奇数，底部如果偶数

虽然这不是我想要的算法，但它极大地改善了组件的视觉外观，使其更具可读性。

老

​

新

​

老

新

​

老

新

​

Answer 2

我不确定这是否仍然是一个问题，但如果是，您能详细说明什么“行->行”关系吗？对于哪些节点属于哪一行，这是一个严格的定义吗？最近版本的d3-dag支持节点的等级标准，它为节点行指定了相等约束的相对顺序，但这可能不是您要寻找的。

如果你只想重新定位边缘，可能有办法拉出d3-dag的内部，只需做交叉最小化。从本质上说，d3完成了大多数分层布局所做的工作，将边缘划分为各节，并更改每一行中每条边的顺序。在设置了顺序之后，就可以很容易地分配坐标。如果你能这样表达你的问题，你应该能够使用像这这样的代码来把它描述成一个整数线性规划，并找到最优的边缘布局。