6

Processing を使用して、複雑なデータとプロセスのナビゲーション システムを開発しています。その一環として、私はグラフ レイアウトにかなり深く入り込みました。それはすべて楽しいものであり、レイアウトアルゴリズムに関する私の意見は次のとおりです。強制指向は弱虫向けです（スケールを見てください...笑）、固有ベクトル投影はクールです、杉山レイヤーは見栄えがしますが、グラフィーグラフでは速く失敗します。これまでの固有ベクトルでは、エッジの交差を最小限に抑えて、実際にデータのポイントに到達する必要があります。私は知っています、私はNP完全などを知っています。

xyボクシングを適用し、杉山のような順列を使用して、行と列をまたがるエッジの交差を減らすことで、ある程度の成功を収めたことを付け加えておきます。Viz: グラフ (|V|=90,avg degree log|V|) は、交差を減らすために行と列の置換を交互に行うことにより、11000 の交差 -> 1500 (箱入りの固有ベクトルによる) -> 300 に進むことができます。

しかし、極小値は... それが何であれ、このマークの周りに留まり、結果は可能な限り明確ではありません. 光に関する私の研究は、VLSI で使用されているような平坦化アルゴリズムを本当に使用したいことを示唆しています。

  1. BFS などを使用して、最大平面サブグラフ 1.a を作成します。平面サブグラフをナイスライクにレイアウトする
  2. 卓越したエッジを巧みに追加して元のグラフを復元する

最速の平坦化アルゴリズムについての考えを返信してください。よく知っている特定の最適化について詳しく説明してください。

本当にありがとう！

4

2 に答える 2

3

すべてのグラフが平面ではないことを考えると (ご存知のように)、「常に最良の回答を提供する」アプローチよりも「次善の」アプローチを採用する方がよい場合があります。

私がこれを言うのは、大学院のルームメイトがあなたと同じ問題を抱えていたからです。彼はグラフを平面形式に変換しようとしていましたが、最小エッジ交差を保証するすべてのアルゴリズムが遅すぎました。彼が最終的に行ったことは、ランダム化されたアルゴリズムを実装しただけです。基本的には、グラフをレイアウトしてから、多数の交差があるエッジを持つジガー ノードを配置し、最終的に最悪のエッジの塊を処理します。

利点は次のとおりです。特定の時間が経過したら切り取ることができるため、時間が制限されている場合、これは常に一定の時間内に収まります。レイアウトされたグラフ) より良いものを得ることができ、コーディングは比較的簡単です。

欠点は、交差で常にグローバルな最小値が得られるとは限らないことです。グラフが高い交差領域でスタックした場合、彼のアルゴリズムはノードを遠くに放ち、それを解決しようとすることがあります。これにより、非常に奇妙なグラフが表示されることがあります。 .

于 2011-11-18T14:56:31.250 に答える
2

あなたはすでに多くのグラフ レイアウトを知っていますが、残念ながら、あなたの質問はまだ特定されていないと思います。

次のことを行うことで、グラフを非常に迅速に平面化できます: (1) 平面上にグラフをランダムにレイアウトします (2) エッジが交差する場所を計算します (3) 交差点で疑似頂点を作成します (これは、平面性を使用するときにとにかく行うことです)非平面グラフのベース レイアウト) (4) 新しい頂点と分割されたエッジで拡張されたグラフは、自動的に平面になります。

最初の難しさは、エッジ交差の数を最小限に抑える組み合わせ埋め込みを計算するアルゴリズムを持つことから生じます。2 番目の問題は、その組み合わせ埋め込みを使用して、視覚的に魅力的なユークリッド平面でのレイアウトを行うことです。たとえば、直交グラフ レイアウトでは、曲がりの数を最小限に抑え、面のサイズを最大化し、グラフ全体の面積を最小化したい場合があります。など、これらの目標は互いに矛盾する可能性があります。

于 2011-11-19T01:49:21.993 に答える