Zeichnung Gerichtete Azyklische Graphen: Minimierung des edge crossing?

Auslegen der verticies in einer DAG ist in einer Baumstruktur (d.h. verticies mit keine Ränder oben, verticies halt nur auf die auf die nächste Ebene, etc.) ist eher einfach und ohne graph-drawing-algorithmen wie Effizient Sugiyama. Jedoch gibt es einen einfachen Algorithmus, um dies zu tun, minimiert edge crossing? (Für einige Graphen, kann es unmöglich sein, vollständig zu eliminieren edge-Kreuzung.) Ein Bild sagt mehr als tausend Worte, gibt es also einen Algorithmus, der würde vorschlagen,etwas ohne kreuzende Kanten. (im Vergleich zu dieser).

EDIT: Das Ergebnis

Ich angenommen habe Senthil ist, was darauf hindeutet, graphviz/dot -- ein kurzer Blick auf die docs bestätigt, dass es sehr einfach zu verwenden Sie es als eine Bibliothek oder ein externes tool, und das Ausgabeformat ist überraschend leicht zu analysieren. Aber ich landete die Wahl zu verwenden GraphSharp statt, da ich bereits mit .NET, etc (obwohl es definitiv nicht so mächtig wie die dot). Das Ergebnis ist "gut genug" sein, und könnte gemacht werden viel besser mit ein wenig edge-routing-und tweaking (der text verschwommen ist, weil der 3.5 WPF).

Automatisch formatierte Diagramm http://public.blu.livefilestore.com/y1pEY8I95GtlzcxZzhDMhhKoUyejT_sVVZ4jlsDK2fdl6XAR4WV4-yuSesY6chXokmAZxdJXZ4Bv674TqwpT1-fOg/dag3.gif

Hier ist die komplette C# - code (das ist der gesamte code, die Verweise entweder QuickGraph oder GraphSharp -- ja; es war so einfach):

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; } }
    }
  • Ich dachte, die Sugiyama-Methode ist soll minimiert edge crossings? Vielleicht ist das "Efficient" - version, die Sie erwähnt außer acht gelassen, dass Schritt.
  • Larson - Yup; ich könnte mit einem layout-Algorithmus wie das, aber ich Frage mich, ob gab es keine, könnten sich die Vorteile des azyklischen Eigenschaften des Graphen (und würde immer Punkten, vor diejenigen von Ihnen abhängig)
Schreibe einen Kommentar