描かれた非環式グラフの描画：エッジの交差を最小化しますか？

Question

ヴァージーを木の形の垂直にレイアウトする（つまり、上にインエッジがない垂直、次のレベルのもののみに依存するヴァージーなど）は、効率的な杉山などのグラフ描画アルゴリズムなしでかなり単純です。しかし、これを行うための簡単なアルゴリズムはあります。 （一部のグラフの場合、エッジの交差を完全に排除することは不可能かもしれません。）写真は千の単語を書いているので、提案するアルゴリズムがあります。 エッジを渡ることのない何か. (これと比較して).

編集：結果

Senthilの提案GraphViz/Dotを受け入れました - ドキュメントを簡単に見ると、それが非常に簡単であることを確認します ライブラリまたは外部ツールとして使用します, 、 と 出力形式は驚くほど簡単に解析できます. 。しかし、私は最終的に使用することを選択しました GraphSharp 代わりに、私はすでに.NETなどを使用しているので（それは間違いなくDOTほど強力ではありませんが）。結果は「十分」であり、少しエッジのルーティングと微調整ではるかに良くなる可能性があります（ぼやけたテキストは原因です 3.5 WPF).

レイアウトグラフhttp://public.blu.livefilestore.com/y1pey8i95gtlzcxzzhdmhhhkouyejt_svvz4jlsdk2ffdl6xar4wv4-yusesy6chxokmazxdjxzzz4vvvvv674tqwpt1-fog/dagfog/dagfog

これが次のとおりです 完了 C＃コード（これは、QuickGraphまたはGraphSharpのいずれかを参照するすべてのコードです - ええ;それは簡単でした）：

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-「階層」または指示されたグラフのレイヤード図面。レイアウトアルゴリズムは、エッジを同じ方向（上から下、または左から右）に向け、エッジの交差を避けてエッジの長さを減らすことを試みます。

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

Answer 2

使用してみてください トポロジーソート. 。最初のステップでは、トポロジー種を実行し、常に単一層で独立したノードをグループ化することにより、レイアウトのレベル（上から下）を決定できます。これは、指示された非環式グラフで常に成功します。

次に、入力ポートと出力ポートの位置を取得し、おそらく隣接するレイヤーを考慮に入れて、各レイヤー（左から右）のトポロジカルな種類を実行しようとするかもしれません。このステップの私のイメージは少しぼやけていますが、あなたの例のようなグラフで実行可能であると想像できます。