10

プレゼンテーションから:3ページのグラフとツリーは、Reigngold-Tilfordプロセス中に何が起こっているかを視覚的に示しています。また、事前にこのアルゴリズムのあいまいな要約を示します。"...starts with bottom-up pass of the tree; [finishes with] Top-down pass for assignment of final positions..."再帰的手段を介して両方の方向パスを実現でき、Y値は各ノードの生成レベルに対応していることはわかっていますが、それでも方法については迷っています。 X座標が解かれます。

私はこのプロジェクトに出くわしました:WPFのグラフツリー描画コントロールですが、コードが非常に多いため、X値を定義するための単純な2〜3のメソッドを見つけるのに非常に苦労しました。(WPFの経験もありません)

私はこれを行う方法を数日間検索して実験してきましたので、あなたの助けに大いに感謝します!

4

2 に答える 2

43

jwpat7の回答に記載されている記事は非常に便利ですが、このアルゴリズムに必要な正確なロジックを理解するのに時間がかかったので、説明を簡単にするために独自のブログ投稿を作成しました。

Xノードの位置を決定する方法のプレーンテキストロジックは次のとおりです。

  • ツリーの注文後のトラバーサルから開始します

  • セットの最初のノードである場合、またはそうでない場合は、0の各ノードに初期X値を割り当てますpreviousSibling + 1

    ここに画像の説明を入力してください

  • ノードに子がある場合は、その子を中心とする目的のX値を見つけます。

    • ノードが左端のノードである場合は、そのXをその値に設定します

    • ノードが左端のノードでない場合は、すべての子をシフトしてこのノードの下の中央に配置するためにMod、ノードのプロパティをに設定します。(X - centeredX)ツリーの最後のトラバーサルは、このModプロパティを使用して、各ノードの最終的なX値を決定します。

  • このノードの子のいずれかが、このノードの左側にある兄弟の子とオーバーラップするかどうかを判別します。基本的に、各Yについて、2つのノードから最大および最小のXを取得し、それらを比較します。

    • 衝突が発生した場合は、必要に応じてノードをシフトします。サブツリーをシフトするには、ノードのプロパティXとプロパティを追加するだけです。Mod

    • ノードがシフトされた場合は、重なり合っていた2つのサブツリー間でノードもシフトして、等間隔に配置します。

  • 最終的なXが計算されるときに、負のX値がないことを確認するためのチェックを実行します。見つかった場合は、最大のものをルートノードXModプロパティに追加して、ツリー全体をシフトオーバーします

  • 事前順序トラバーサルを使用してツリーの2回目のトラバーサルをMod実行し、ノードの各親からの値の合計をそのXプロパティに追加します

上記のツリーの最終的なX値は、次のようになります。

ここに画像の説明を入力してください

ブログ投稿に詳細とサンプルコードがいくつかありますが、ここにすべてを含めるには長すぎるため、コードの詳細ではなく、アルゴリズムのロジックに焦点を当てたいと思いました。

于 2014-04-21T15:36:38.983 に答える
4

コードを含むいくつかの記事が利用可能です。Pythonはbillmill.orgにあり、Cは1991年2月1日のDr.Dobb'sJournalの記事の2ページにあります。。あなたは「単純な2〜3の方法」(おそらく料理本の方法を意味する)を求めましたが、一般的に木をうまく描くことはNP完全問題です(Supowit、KJ、EM Reingold、「木をうまく描くことの複雑さ」、Actaを参照) Informatica 18、4、1983年1月、377-392、DDJ記事の参照4)。Reingold–Tilford法は、線形時間で二分木を多かれ少なかれうまく描画し、Buchheimのバリエーションは、線形時間でn-ary木を多かれ少なかれうまく描画します。ただし、ビルミルの記事では、(原則6を述べた直後に)「この記事で単純なアルゴリズムを検討するたびに、それが不十分であることがわかりました...」と指摘しているため、より単純な方法が機能する可能性があります。 OKは小さいです。

于 2012-10-29T21:11:27.417 に答える