是否有允许固定一个轴上的位置的 DAG 二维布局算法？
Is there a 2D-layout algorithm for DAGs that allows the positions on one axis to be fixed?
我有一个大约有 3.300 个顶点的 DAG，dot 可以非常成功地将其布局为一棵或多或少简单的树（事情变得复杂，因为顶点可以有一个以上的前任从一个整体不同的排名，所以交叉很频繁）。图中的每个顶点在原始过程中的特定时间出现，我希望布局中的一个轴表示时间：像 a -> v, b -> v 这样的边缘关系意味着 a 和 b在 v.
之前的某个特定时间出现
是否有 DAG 布局算法允许我指定一个轴上的位置（或至少是距离）并针对另一轴上的边缘交叉提出最佳布局？
您可以创建一个 topological sorting of the DAG 来对顶点进行排序，对于每条边 x->y，顶点 x 都在 y 之前。
因此，如果您有 a -> v, b -> v，您将得到类似 a, b, v 或 b, a, v 的结果。
使用这个你可以很容易地表示 DAGs 这样的：
如果我对您的理解正确，那么您希望最大限度地减少图形布局中的边交叉数。如果是，那么答案是"No"，因为这个问题在一般情况下被证明是NP完全的。参见 this、"Crossing Number is NP-Complete, Garey, Johnson"。
如果您需要一个不是最佳但足够好的解决方案，有多篇关于此主题的文章，因为它与电路布局密切相关。可能谷歌搜索 "crossing number heuristics" 并浏览一些论文的摘要会比我试图盲目猜测你的要求更好地解决你的任务。
是的，正如@Arturo-Menchaca 所说，拓扑排序可能有助于减少边的重叠数。但它可能不是最优的。边缘交叉最小化没有好的算法。交叉最小化的问题是 NP 完全问题。启发式方法用于解决这个问题。
这个 Whosebug link 可能对您有帮助：Drawing Directed Acyclic Graphs: Minimizing edge crossing?
我想您的问题与图形布局的美观方式有关。文章 Overview of algorithms for graph drawing, Force-Directed Drawing Algorithms 中描述了一些启发式方法。可能有关平面图或几乎平面图的信息也可以帮助您。
Wiki 页面中描述了检查和绘制平面图的算法的一些回顾Planar graph, Crossing number (graph theory). The libraries and algorithms for planar graph drawing are described in the Whosebug question How to check if a Graph is a Planar Graph or not? For example the author in the article GA for straight-line grid drawings of maximal planar graphs使用遗传算法绘制直线网格。
文章 Straight-Line Drawability of a Planar Graph Plus an Edge, On the Crossing Number of Almost Planar Graphs.
中对几乎平面图进行了很好的描述
尝试使用您的单轴对齐条件修改原始算法。
我有一个大约有 3.300 个顶点的 DAG，dot 可以非常成功地将其布局为一棵或多或少简单的树（事情变得复杂，因为顶点可以有一个以上的前任从一个整体不同的排名，所以交叉很频繁）。图中的每个顶点在原始过程中的特定时间出现，我希望布局中的一个轴表示时间：像 a -> v, b -> v 这样的边缘关系意味着 a 和 b在 v.
是否有 DAG 布局算法允许我指定一个轴上的位置（或至少是距离）并针对另一轴上的边缘交叉提出最佳布局？
您可以创建一个 topological sorting of the DAG 来对顶点进行排序，对于每条边 x->y，顶点 x 都在 y 之前。
因此，如果您有 a -> v, b -> v，您将得到类似 a, b, v 或 b, a, v 的结果。
使用这个你可以很容易地表示 DAGs 这样的：
如果我对您的理解正确，那么您希望最大限度地减少图形布局中的边交叉数。如果是，那么答案是"No"，因为这个问题在一般情况下被证明是NP完全的。参见 this、"Crossing Number is NP-Complete, Garey, Johnson"。
如果您需要一个不是最佳但足够好的解决方案，有多篇关于此主题的文章，因为它与电路布局密切相关。可能谷歌搜索 "crossing number heuristics" 并浏览一些论文的摘要会比我试图盲目猜测你的要求更好地解决你的任务。
是的，正如@Arturo-Menchaca 所说，拓扑排序可能有助于减少边的重叠数。但它可能不是最优的。边缘交叉最小化没有好的算法。交叉最小化的问题是 NP 完全问题。启发式方法用于解决这个问题。
这个 Whosebug link 可能对您有帮助：Drawing Directed Acyclic Graphs: Minimizing edge crossing?
我想您的问题与图形布局的美观方式有关。文章 Overview of algorithms for graph drawing, Force-Directed Drawing Algorithms 中描述了一些启发式方法。可能有关平面图或几乎平面图的信息也可以帮助您。
Wiki 页面中描述了检查和绘制平面图的算法的一些回顾Planar graph, Crossing number (graph theory). The libraries and algorithms for planar graph drawing are described in the Whosebug question How to check if a Graph is a Planar Graph or not? For example the author in the article GA for straight-line grid drawings of maximal planar graphs使用遗传算法绘制直线网格。
文章 Straight-Line Drawability of a Planar Graph Plus an Edge, On the Crossing Number of Almost Planar Graphs.
中对几乎平面图进行了很好的描述尝试使用您的单轴对齐条件修改原始算法。