Disegno di grafici aciclici diretti:Ridurre al minimo l'attraversamento dei bordi?

Question

Disposizione dei vertici in un DAG sotto forma di albero (ad es.vertici senza bordi interni in alto, vertici dipendenti solo da quelli del livello successivo, ecc.) è piuttosto semplice senza algoritmi di disegno grafico come Efficient Sugiyama.Tuttavia, esiste un semplice algoritmo per farlo che riduca al minimo l'attraversamento dei bordi?(Per alcuni grafici, potrebbe essere impossibile eliminare completamente l'incrocio dei bordi.) Un'immagine dice più di mille parole, quindi esiste un algoritmo che suggerirebbe qualcosa senza oltrepassare i bordi. (rispetto a questo).

MODIFICARE:Il risultato

Ho accettato il suggerimento di Senthil graphviz/dot: una rapida occhiata ai documenti conferma che è molto facile da usarlo come libreria o strumento esterno, E il formato di output è sorprendentemente facile da analizzare.Tuttavia, ho finito per scegliere di utilizzare GraphSharp invece poiché sto già utilizzando .NET, ecc. (anche se sicuramente non è potente come punto).Il risultato è "abbastanza buono" e potrebbe essere migliorato con un po' di instradamento e modifica dei bordi (il testo sfocato è a causa di 3.5WPF).

Grafico strutturato automaticamente http://public.blu.livefilestore.com/y1pEY8I95GtlzcxZzhDMhhKoUyejT_sVVZ4jlsDK2fdl6XAR4WV4-yuSesY6chXokmAZxdJXZ4Bv674TqwpT1-fOg/dag3.gif

Ecco il completare Codice C# (questo è tutto il codice che fa riferimento a QuickGraph o GraphSharp -- sì;è stato così facile):

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 sembra che sarebbe adatto al conto:

dot - ''gerarchico'' o stratificato disegni di grafi diretti.Le l'algoritmo di layout punta i bordi nel stessa direzione (dall'alto verso il basso o a sinistra a destra) e poi tenta di evitare incroci dei bordi e ridurre la lunghezza dei bordi.

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

Answer 2

Potresti provare a usare Ordinamento topologico.In un primo passaggio è possibile determinare i livelli (dall'alto al basso) del layout eseguendo un ordinamento topologico e raggruppando sempre i nodi indipendenti in un unico layer.Ciò avrà sempre successo per i grafi aciclici diretti.

Quindi potresti provare a eseguire un ordinamento topologico di ciascun livello (da sinistra a destra) tenendo conto della posizione delle porte di input e output e probabilmente degli strati adiacenti.La mia immagine di questo passaggio è un po' sfocata, ma posso immaginare che sia fattibile per grafici come il tuo esempio.