绘制有向无环图：最小化边缘交叉？

Question

以树的形式布置 DAG 中的顶点（即顶部没有内边的顶点、仅依赖于下一层的顶点等）在没有诸如 Efficient Sugiyama 之类的图形绘制算法的情况下相当简单。然而，是否有一种简单的算法可以做到这一点，最大限度地减少边缘交叉？（对于某些图，可能无法完全消除边缘交叉。）一张图片可以表达一千个单词，那么是否有一种算法可以建议 没有交叉边缘的东西. (与此相比).

编辑：结果

我已经接受了 Senthil 的建议 graphviz/dot ——快速浏览一下文档证实它很容易 将其用作库或外部工具, ， 和 输出格式非常容易解析. 。然而，我最终选择使用 图形锐利 相反，因为我已经在使用 .NET 等（尽管它绝对不如 dot 那么强大）。结果是“足够好”，并且可以通过一些边缘路由和调整来做得更好（模糊的文本是因为 3.5 WPF).

自动布局图http://public.blu.livefilestore.com/y1pEY8I95GtlzcxZzhDMhhKoUyejT_sVVZ4jlsDK2fdl6XAR4WV4-yuSesY6chXokmAZxdJXZ4Bv674TqwpT1-fOg/dag3.gif

这是 完全的 C# 代码（这是引用 QuickGraph 或 GraphSharp 的所有代码——是的；就是这么简单）：

internal static class LayoutManager
{
    private const string ALGORITHM_NAME = "EfficientSugiyama";
    private const bool MINIMIZE_EDGE_LENGTH = true;
    private const double VERTEX_DISTANCE = 25;
    private const double LAYER_DISTANCE = 25;
    private const double MIN_CANVAS_OFFSET = 20;

    public static void doLayout(GraphCanvas canvas)
    {
        // TODO use a background thread
        // TODO add comments
        canvas.IsEnabled = false;
        canvas.Cursor = Cursors.Wait;
        var graph = new BidirectionalGraph<GraphNode, LayoutEdge>();
        var positions = new Dictionary<GraphNode, Point>();
        var sizes = new Dictionary<GraphNode, Size>();
        foreach(var node in canvas.nodes)
        {
            var size = node.RenderSize;
            graph.AddVertex(node);
            positions.Add(node, new Point(node.left + size.Width / 2, node.top + size.Height / 2));
            sizes.Add(node, size);
        }
        foreach(var edge in canvas.edges)
        {
            graph.AddEdge(new LayoutEdge(edge));
        }

        var context = new LayoutContext<GraphNode, LayoutEdge, BidirectionalGraph<GraphNode, LayoutEdge>>(graph, positions, sizes, LayoutMode.Simple);
        var parameters = new EfficientSugiyamaLayoutParameters();
        parameters.VertexDistance = VERTEX_DISTANCE;
        parameters.MinimizeEdgeLength = MINIMIZE_EDGE_LENGTH;
        parameters.LayerDistance = LAYER_DISTANCE;
        var factory = new StandardLayoutAlgorithmFactory<GraphNode, LayoutEdge, BidirectionalGraph<GraphNode, LayoutEdge>>();
        var algorithm = factory.CreateAlgorithm(ALGORITHM_NAME, context, parameters);
        algorithm.Compute();
        canvas.deselectAll();

        var minx = algorithm.VertexPositions.Select(kvp => kvp.Value.X - (kvp.Key.RenderSize.Width / 2)).Aggregate(Math.Min);
        var miny = algorithm.VertexPositions.Select(kvp => kvp.Value.Y - (kvp.Key.RenderSize.Height / 2)).Aggregate(Math.Min);
        minx -= MIN_CANVAS_OFFSET;
        miny -= MIN_CANVAS_OFFSET;
        minx = minx < 0 ? -minx : 0;
        miny = miny < 0 ? -miny : 0;
        foreach(var kvp in algorithm.VertexPositions)
        {
            var node = kvp.Key;
            var pos = kvp.Value;
            node.left = (pos.X - (node.RenderSize.Width / 2)) + minx;
            node.top = (pos.Y - (node.RenderSize.Height / 2)) + miny;
        }
        canvas.Cursor = Cursors.Arrow;
        canvas.IsEnabled = true;
    }

    private sealed class LayoutEdge : IEdge<GraphNode>
    {
        private readonly ConnectingEdge _edge;
        public LayoutEdge(ConnectingEdge edge) { _edge = edge; }
        public GraphNode Source { get { return _edge.output.node; } }
        public GraphNode Target { get { return _edge.input.node; } }
    }

Answer 1

Dot 似乎符合要求：

点 - ``层次结构''或有向图的分层图。布局算法的瞄准边缘朝着相同的方向（上到底或从左到右），然后尝试避免边缘交叉并降低边缘长度。

https://docs.google.com/viewer?url=http://www.graphviz.org/pdf/dotguide.pdf

Answer 2

你可以尝试使用 拓扑排序. 。第一步，您可以通过执行拓扑排序并始终将独立节点分组在单个层中来确定布局的级别（从上到下）。对于有向无环图来说，这总是会成功。

然后，您可以尝试对每一层（从左到右）执行拓扑排序，同时考虑输入和输出端口的位置以及可能相邻的层。我对这一步的印象有点模糊，但我可以想象它对于像你的例子这样的图表是可行的。