本文介绍了绘制有向无环图:最小化边交叉?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

以树的形式布置 DAG 中的顶点(即顶部没有入边的顶点,顶点仅依赖于下一层的顶点等)相当简单,无需图形绘制算法,例如 Efficient Sugiyama.但是,是否有一种简单的算法可以最大限度地减少边缘交叉?(对于某些图形,可能无法完全消除边缘交叉.)一张图说了一千个字,那么是否有一种算法可以建议 没有交叉边缘的东西.(noparr7c7A"">noparrn reln 结果

我接受了 Senthil 的建议使用 graphviz/dot -- 快速浏览一下文档可以确认 将其用作库或外部工具,以及 输出格式非常容易解析.但是,我最终选择使用 GraphSharp 代替,因为我已经在使用 .NET 等(尽管它是绝对没有点那么强大).结果是足够好",并且可以通过一些边缘路由和调整来做得更好(模糊的文本是因为 3.5 WPF).

这是完整的 C# 代码(这是所有引用 QuickGraph 或 GraphSharp 的代码——是的;就是这么简单):

内部静态类LayoutManager{private const string ALGORITHM_NAME = "EfficientSugiyama";private const bool MINIMIZE_EDGE_LENGTH = true;私人常量双VERTEX_DISTANCE = 25;私有常量双 LAYER_DISTANCE = 25;私有常量双 MIN_CANVAS_OFFSET = 20;public static void doLayout(GraphCanvas canvas){//TODO 使用后台线程//TODO 添加注释canvas.IsEnabled = false;canvas.Cursor = Cursors.Wait;var graph = new BidirectionalGraph();var position = new Dictionary();var size = new Dictionary();foreach(canvas.nodes 中的 var 节点){var size = node.RenderSize;graph.AddVertex(节点);position.Add(node, new Point(node.left + size.Width/2, node.top + size.Height/2));大小.添加(节点,大小);}foreach(canvas.edges 中的 var 边){graph.AddEdge(new LayoutEdge(edge));}var context = new LayoutContext>(图形,位置,大小,LayoutMode.Simple);var parameters = new EfficientSugiyamaLayoutParameters();parameters.VertexDistance = VERTEX_DISTANCE;parameters.MinimizeEdgeLength = MINIMIZE_EDGE_LENGTH;parameters.LayerDistance = LAYER_DISTANCE;var factory = new StandardLayoutAlgorithmFactory>();var algorithm = factory.CreateAlgorithm(ALGORITHM_NAME, context, parameters);算法.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;最小 -= MIN_CANVAS_OFFSET;minx = minx {私有只读 ConnectingEdge _edge;公共 LayoutEdge(ConnectingEdge 边缘){ _edge = 边缘;}public GraphNode Source { get { return _edge.output.node;} }公共 GraphNode 目标 { 获取 { 返回 _edge.input.node;} }}
解决方案

Dot 看起来很合适:

dot - 分层"或分层有向图的绘制.这布局算法的目标是边缘相同的方向(从上到下,或左向右),然后试图避免边缘交叉并减少边缘长度.

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

Laying out the verticies in a DAG in a tree form (i.e. verticies with no in-edges on top, verticies dependent only on those on the next level, etc.) is rather simple without graph drawing algorithms such as Efficient Sugiyama. However, is there a simple algorithm to do this that minimizes edge crossing? (For some graphs, it may be impossible to completely eliminate edge crossing.) A picture says a thousand words, so is there an algorithm that would suggest something without crossing edges. (compared to this).

EDIT: The result

I've accepted Senthil's suggesting graphviz/dot -- a quick look at the docs confirms that it's very easy to use it as a library or external tool, and the output format is surprisingly easy to parse. However, I ended up choosing to use GraphSharp instead since I'm already using .NET, etc (though it's definitely not as powerful as dot). The result is "good enough", and could be made a lot better with a little edge routing and tweaking (the blurry text is because of 3.5 WPF).

Automatically layed-out graph http://public.blu.livefilestore.com/y1pEY8I95GtlzcxZzhDMhhKoUyejT_sVVZ4jlsDK2fdl6XAR4WV4-yuSesY6chXokmAZxdJXZ4Bv674TqwpT1-fOg/dag3.gif

Here's the complete C# code (this is all the code that references either QuickGraph or GraphSharp -- yeah; it was that easy):

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; } }
    }
解决方案

Dot seems like it would fit the bill:

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

这篇关于绘制有向无环图:最小化边交叉?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

07-30 05:16