Desenho gráficos aciclicos direcionados: minimizando a passagem de borda?

Question

Estabelecer as verticas em um DAG em uma forma de árvore (ou seja, verticals sem arestas no topo, as vertículas dependem apenas daquelas no próximo nível, etc.) é bastante simples sem algoritmos de desenho de gráficos, como sugiyama eficiente. No entanto, existe um algoritmo simples para fazer isso que minimiza a passagem de borda? (Para alguns gráficos, pode ser impossível eliminar completamente o cruzamento de arestas.) Uma imagem diz mil palavras, então existe um algoritmo que sugeriria algo sem cruzar as bordas. (comparado a isso).

Editar: o resultado

Eu aceitei o Graphviz/Dot sugerido de Senthil - uma rápida olhada nos documentos confirma que é muito fácil Use -o como uma biblioteca ou ferramenta externa, e O formato de saída é surpreendentemente fácil de analisar. No entanto, acabei escolhendo usar GraphSharp Em vez disso, já que já estou usando .NET, etc (embora definitivamente não seja tão poderoso quanto o DOT). O resultado é "bom o suficiente" e pode ser melhorado com um pouco de roteamento e ajustes (o texto embaçado é por causa de 3.5 WPF).

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

Aqui está o completo Código C# (este é todo o código que faz referência ao QuickGraph ou GraphSharp - sim; foi tão fácil):

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 parece que se encaixaria na conta:

DOT - `` hierárquico '' ou desenhos em camadas de gráficos direcionados. O algoritmo de layout aponta as bordas na mesma direção (de cima para baixo ou da esquerda para a direita) e, em seguida, tenta evitar cruzamentos de borda e reduzir o comprimento da borda.

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

Answer 2

Você poderia tentar usar Classificação topológica. Em uma primeira etapa, você pode determinar os níveis (de cima para baixo) do layout, executando uma classificação topológica e sempre agrupando nós independentes em uma única camada. Isso sempre terá sucesso para gráficos aciclicos direcionados.

Talvez você possa tentar executar um tipo topológico de cada camada (da esquerda para a direita) levando em consideração a localização das portas de entrada e saída e provavelmente camadas adjacentes. Minha imagem desta etapa é um pouco embaçada, mas posso imaginar que é factível para gráficos como o seu exemplo.