Zeichnung Directed azyklische Graphen: Minimierung Kreuzung Rand?

Question

legen die verticies in einem DAG in einer Baumform aus (das heißt verticies ohne in-Kanten auf, abhängig verticies nur auf diejenigen, auf die nächste Ebene, etc.) ist ziemlich einfach ohne Zeichnen von Graphen-Algorithmen wie Efficient Sugiyama. Allerdings gibt es einen einfachen Algorithmus diese dass mindernd Rand Kreuzung zu tun? (Für einige grafischen Darstellungen, kann es unmöglich sein, vollständig Rand Kreuzung zu beseitigen.) Ein Bild sagt mehr als tausend Worte, so gibt es einen Algorithmus, der etwas ohne Kanten überqueren . ( auf diese verglichen).

EDIT: Das Ergebnis

Ich habe Senthil die akzeptiert was darauf hindeutet, graphviz / Punkt - einen kurzen Blick auf die Dokumentation bestätigt, dass es sehr leicht zu verwenden sie es als Bibliothek oder externes Tool und GraphSharp statt, da ich bereits .NET, etc. (obwohl es auf jeden Fall nicht so mächtig wie Punkt). Das Ergebnis ist „gut genug“, und könnte viel besser mit einem wenig Fräsrand und Tweaking (der verschwommene Text ist wegen 3.5 WPF ).

automatisch verlegt-out Graph http: //public.blu. livefilestore.com/y1pEY8I95GtlzcxZzhDMhhKoUyejT_sVVZ4jlsDK2fdl6XAR4WV4-yuSesY6chXokmAZxdJXZ4Bv674TqwpT1-fOg/dag3.gif

Hier ist der vollständig C # -Code (dies ist der gesamte Code, dass 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; } }
    }

Answer 1

Dot scheint, wie es die Rechnung passen würde:

  

dot - `` hierarchische '' oder geschichtet   Zeichnungen von gerichteten Graphen. Das   Layout-Algorithmus Ziele Kanten in der   derselben Richtung (von oben nach unten oder von links   nach rechts) und dann versucht zu vermeiden   Kantenkreuzungen und Kantenlänge reduzieren.

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

Answer 2

Sie könnten versuchen, Topologische Sortierung . In einem ersten Schritt können Sie die Ebene (von oben nach unten) des Layout bestimmen, indem eine topologische Sortierung durchführt und immer Gruppierung unabhängige Knoten in einer einzigen Schicht. Dies wird immer für eine gerichtete azyklische Graphen erfolgreich zu sein.

Dann könnte man vielleicht versuchen, eine topologische Sortierung jeder Schicht durchzuführen (von links nach rechts), um die Position der Eingangs- und Ausgangsanschlüsse und wahrscheinlich benachbarter Schichten zu berücksichtigen. Mein Bild von diesem Schritt etwas unscharf, aber ich kann mir vorstellen, dass es für grafische Darstellungen wie Ihr Beispiel machbar ist.