Dibujo Dirigido acíclicos Gráficos: Reducción al mínimo del borde de cruce?

Question

Trazado de los vértices en un DAG en forma de árbol (es decir vértices sin in-bordes en la parte superior, vértices dependientes sólo en aquellos en el siguiente nivel, etc.) es bastante simple y sin dibujo gráfico algoritmos tales como Efficient Sugiyama. Sin embargo, no es un algoritmo simple de hacer esto que cruce el borde reduce al mínimo? (Para algunos gráficos, puede ser imposible eliminar por completo cruce borde.) Una imagen dice mil palabras, por lo que hay un algoritmo que sugeriría algo sin cruzar bordes . ( comparado con este ).

EDIT: El resultado

He aceptado lo que sugiere graphviz / punto de Senthil - un rápido vistazo a la documentación confirma que es muy fácil de usarlo como una biblioteca o una herramienta externo, y el formato de salida es sorprendentemente fácil de analizar . Sin embargo, terminé la elección de utilizar GraphSharp lugar ya que ya estoy usando .NET, etc (aunque es definitivamente no es tan poderoso como el punto). El resultado es "suficientemente bueno", y se podría hacer mucho mejor con el encaminamiento y ajustar un poco de borde (el texto es borrosa debido a la 3.5 WPF ).

layed de salida automáticamente gráfico http: //public.blu. livefilestore.com/y1pEY8I95GtlzcxZzhDMhhKoUyejT_sVVZ4jlsDK2fdl6XAR4WV4-yuSesY6chXokmAZxdJXZ4Bv674TqwpT1-fOg/dag3.gif

Aquí está la completa de código C # (esto es todo el código que hace referencia a cualquiera de QuickGraph o GraphSharp - sí, era tan 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 cabría la cuenta:

  

dot - `` jerárquico '' o en capas   dibujos de gráficos dirigidos. los   de diseño de algoritmos objetivos bordes de la   misma dirección (de arriba a abajo, o izquierda   a derecha) y los intentos entonces para evitar   cruces de borde y reducir la longitud de borde.

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

Answer 2

Se podría tratar de usar topológica Clasificación . En un primer paso que puede determinar los niveles (de arriba abajo) de la disposición mediante la realización de una ordenación topológica y siempre agrupación de nodos independientes en una sola capa. Esto siempre tendrá éxito para grafos dirigidos acíclicos.

A continuación, tal vez podría tratar de realizar una ordenación topológica de cada capa (de izquierda a derecha) teniendo la ubicación de los puertos de entrada y de salida y las capas adyacentes, probablemente en cuenta. Mi imagen de este paso es poco borrosa, pero me imagino que es factible para gráficos como tu ejemplo.