Рисование Направленных Графов без петель: Уменьшение граничного пересечения?

Разметка verticies в DAG в древовидной форме (т.е. verticies без в краях на вершине, verticies зависимый только на verticies на следующем уровне, и т.д.) довольно проста без алгоритмов визуализации графика, таких как Эффективный Sugiyama. Однако есть ли простой алгоритм, чтобы сделать это, которое минимизирует граничное пересечение? (Для некоторых графиков может быть невозможно полностью устранить граничное пересечение.) В изображении говорится тысяча слов, так есть ли алгоритм, который предложил бы что-то, не пересекая края. (по сравнению с этим).

Править: Результат

Я принял предложение Senthil graphviz/dot - беглый взгляд на документы подтверждает, что это очень просто в использовании это как библиотека или внешний инструмент, и выходной формат удивительно легко проанализировать. Однако я закончил тем, что принял решение использовать GraphSharp вместо этого, так как я уже использую.NET, и т.д. (хотя это определенно не столь мощно как точка). Результат "достаточно хорош", и мог быть сделан намного лучше с небольшой граничной маршрутизацией, и тонкая настройка (расплывчатый текст из-за 3.5 WPF).

Автоматически layed график 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();
        var positions = new Dictionary();
        var sizes = new Dictionary();
        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>(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>();
        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
    {
        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; } }
    }