グラフ描画 – ウィキペディア

Posted on by
before-content-x4

グラフィック図面 （Engl。 グラフ図 ）は、幾何学的に実現するグラフを扱うコンピューターサイエンスと個別の数学のトピックです。アルゴリズムは、グラフ図面の中心的な役割であり、特定のグラフのユークリッド空間に2次元埋め込みを計算します。グラフのノードは、通常、ポイント、円、正方形などの単純な幾何学的オブジェクトによって実現されます。 2つのノットの間にエッジがある場合、これは 描く ノードに割り当てられたオブジェクトを接続するヨルダン曲線で表示されます。

after-content-x4

グラフ図は2つのフィールドに分かれています。 静的 グラフが表示されている間にグラフ描画が表示されます 動的 グラフの描画グラフのシーケンス全体（主にアニメーション）を視覚化する必要があります。

グラフ図には、グラフを描くことができる普遍的な手法はありません。アプリケーションの領域に応じて、達成する効果を強調するには、さまざまなアプローチが必要です。以下の説明は、静的グラフィック図面と動的グラフィック図面の両方に適用されます。

階層図 [ 編集 | ソーステキストを編集します ]

ここでは、簡単なグラフから階層を読み取り、それを適切に提示しようとします。この目的のために、結び目の量は同等のクラスに分割されるため、同等のクラスの結び目が高さで描画されます。これにより、グラフで普及する階層を強調する図面が作成されます。

ビジネスプロセスモデリング、階層グラフなど。付加価値チェーン図または組織に使用されます。

最長の道の機器 [ 編集 | ソーステキストを編集します ]

すべての開始ノード（前身のないノード）とエンドノード（後継者のないノード）の間で、開始ノードとエンドノードの間のパスが中間に最大数のノードがあるという組み合わせが決定されます。この最長の経路は、すべてのノードとエッジのアライメントの基礎となり、それにより、直線と整列されている最長のパスにある最長のパスと、最長のパスにある最も長いパスが直線の周りに配置されます。

ビジネスプロセスモデリングでは、最長のパスは最長のパスに向けられています。 EPKに使用されます。
Autolayoutアルゴリズムを使用して最長のパスを計算することは、かなりの開発の可能性を秘めた問題です。

after-content-x4

ソフトウェアモデリングでは、このディスプレイは、BPMNおよびUMLの表記で使用できます。

描画ベースの図面 [ 編集 | ソーステキストを編集します ]

このアプローチは、すべてのノットに作用するモデルに基づいています。これらの力は、エッジを通してこのモデルをもたらします。次に、すべての結び目に作用する全体的な力を決定し、したがって、図面の結び目の位置を受信することができます。このアプローチでは、エッジは常に直線で表されます [初め] 。
さらに、より複雑な数学的または擬似物理モデルを使用して、力の計算に使用できます。それでB.すべてのノードを互いに撃退します（静電力に似ています）。ノットも異なる場合があります 密度 1つ 液体培地 個々のノードが多かれ少なかれシミュレートされる ブースト 経験。このように、グラフの自然に見える、しばしば直感的な解釈可能な図面があります [2] 。

スケッチベースの図面 [ 編集 | ソーステキストを編集します ]

この場合、グラフのスケッチが既にあります。これにより、グラフの写真が作成されます。この方法は、たとえば、カードを簡素化する場合、地図作成で使用されます。特定の場所は地図から除外され、選択した場所の間の通りはエッジで表されます。このグラフの図面では、すべてのノットがマップに既に表示されている位置に描画されます。その後、エッジ（主に直線として）が相互に整列します。結果の画像は、たとえば、旅行スケッチやバスの時刻表として使用できます。

Spektral-layout [ 編集 | ソーステキストを編集します ]

スペクトルレイアウトは、グラフを描くためのアルゴリズムのクラスです。ノードのデカルト座標として、ラプラスマトリックスなどのマトリックスのセルフベクターを使用します。グラフのラプラスマトリックスの2つの最大の、または最小の自尊心と関連する自己担当者が計算され、ノードの配置に使用されます。通常、ノットは2次元レベルに配置されます。より多くの寸法に埋め込むことは、他の自己ベクトルを使用して実行できます。

2次元の場合、行/列は特定の結び目が付いています

私 {displaystyle i}

（対称）ラプラスマトリックスで

l {displaystyle l}

グラフの

バツ {displaystyle x}

– と

と {displaystyle y}

– 調整

私 {displaystyle i}

-1番目と2番目のセルフベクトルのtteエントリ

l {displaystyle l}

。

目的の結果に応じて、図面の種類は次のクラスに分割されます。

直交図 [ 編集 | ソーステキストを編集します ]

グラフのノードの直交接続

直交図面では、エッジは常に角で互いに接続されているポリゴン列車として表示されます。すべてのラインの動きは垂直または水平ですが、図面内で斜めにはありません。例はuです。組織 [3] [4] 。

スプライン図面 [ 編集 | ソーステキストを編集します ]

グラフのノードのスプライン接続

エッジは、ねじれがない湾曲した線で表されます。これは、たとえば、Bezier CurvesやB-Spline Curvesの使用によって達成できます。

この参照の例 [5] [6]

グラフの表現は、視聴者を混乱させるべきではなく、基礎となるグラフの特別な特性を強調する必要があります。プレゼンテーションを計算するアルゴリズムの選択は決定的です。このアルゴリズムは、グラフの最も美的表現を実現することを目的としています。しかし、美的表現と見なされるものは、一方では視聴者の個人的な感覚と、プレゼンテーションの意図された目的に依存します。
ただし、表現の適合性を意図した目的で評価できる測定可能な基準があります。

  • 代表的なデバイスの溶解の影響を受けるノードの最小距離と最小サイズ、
  • 代表的なデバイスの表示面の影響を受けるノードの最大距離と最大サイズ、
  • エッジの長さとノットサイズの分散（同じサイズ、ゴールデンカット、あらゆるサイズで格付け）、
  • エッジクロッシングの数、
  • エッジキンクの数（直交エッジ用）またはエッジベースポイント（スプラインエッジ用）、
  • 隣接するノード間の距離（2つのノットの間の自由領域の尺度として）または
  • サブグラフの水平、垂直、対角線、radialアラインメントまたは同様の構造などの対称。

グラフの特別なプロパティは、たとえば、ソース（着信エッジのないノット）または低い（発信エッジのないノード）の存在です。このプロパティは、特に階層レイアウトのゴリスムまたは最長のパスを整列させるレイアウトアルゴリズムによって強調されています。

の中に 動的 グラフの描画は、連続したグラフがあまり異なって描かれていないことも重要です。たとえば、あるグラフから次のグラフまで保持されるノートは、その位置または少なくとも相対的な配置（水平および垂直ノードの順序）を維持する必要があります。この時点で、グラフはSO -Calledであると想定されています メンタルマップ 視聴者はほとんど無意識に認識しています。目標は、シーケンス全体でメンタルマップを取得することです。メンタルマップの影響は、どのタイプの動的グラフが描画されるかによって異なります。たとえば、アニメーションでは、連続した表現を比較する必要がある一連の個々の画像よりも、より多くの変更に従う方が簡単かもしれません。 [7]

さらなる要件としてのメンタルマップの保存に加えて、動的グラフを描画する問題は、2つの場合にさらに区別できます。静的グラフを描画する必要があるが、入力としてアルゴリズムが完全に使用できるようにする必要があるため、次のグラフのみが描画される動的グラフの場合はそうです。この場合、インタラクティブなグラフィック図面について話します [8] または、このオンライン問題の1つ。オフラインの場合、グラフの完全なシーケンスが利用可能です。 [9] [十]

グラフ図は、グラフに基づいたさまざまな種類の図タイプの自動配置、たとえばビジネスプロセスモデリングやソフトウェアモデリングで使用されます。
図面を作成するためのAutolayoutアルゴリズムは、専門の商用ソフトウェアライブラリにもあります [11] 。

YEDダイアグラムエディターなどのソフトウェアアプリケーションは、階層、フォーチュン、スケッチベースの図面を広範囲にサポートし、静的および動的グラフィックサインの両方を有効にします。

  1. ↑ 強制指向レイアウト（英語） （ 記念 2011年6月21日から インターネットアーカイブ ））
  2. ↑ アジャイルセマンティックネットワーク用のSpace-3次元ディスプレイで見つかりました @初め @2 テンプレート：Dead Link/Co-So.org （ ページは使用できなくなりました。検索してください Webarchiven ）） 情報： リンクは、欠陥として自動的にマークされました。指示に従ってリンクを確認してから、このメモを削除してください。
  3. ↑ 組織チャート （ 記念 2005年5月20日から インターネットアーカイブ ））
  4. ↑ aisee.comグラフェンデータベース（英語） （ 記念 2009年3月13日から インターネットアーカイブ ））
  5. ↑ Unix-Evolution （ 記念 2005年5月20日から インターネットアーカイブ ））
  6. ↑ aisee.comグラフェンデータベース、スプラインの例（英語） （ 記念 2009年3月13日から インターネットアーカイブ ））
  7. ↑ D. Archambault、H。Purchase、B。Pinaud： アニメーション、小さな倍数、および動的グラフにおけるメンタルマップ保存の効果 。の： 視覚化とコンピューターグラフィックスに関するIEEEトランザクション 。 バンド 17 、 いいえ。 4 、1。2011年4月、ISSN 1077-2626 、 S. 539–552 、doi： 10.1109 / TVCG.2010.78 （ IEEE.org [2016年10月20日にアクセス]）。
  8. ↑ スティーブンC.ノース： Dynadagの増分レイアウト 。の： グラフ図 （= コンピューターサイエンスの講義ノート ）。 いいえ。 1027 。 Springer Berlin Heidelberg、1995、ISBN 978-3-540-60723-6、 S. 409–418 、doi： 10.1007/BFB0021824 （ springer.com [2016年10月20日にアクセス]）。
  9. ↑ ディール、ステファン、ゲルグ、カルステン、ケレン、アンドレアス： 予見されたレイアウトを使用してメンタルマップを保存します 。 1. 2001年1月、ISSN 1727-5296 、doi： 10.2312/vissym/vissym01/175-184 （ EG.org [2016年10月20日にアクセス]）。
  10. ↑ ベック、ファビアン、バーチ、マイケル、ディール、ステファン、ワイコプフ、ダニエル： 動的グラフを視覚化する際の最先端 。 2014年1月1日、doi： 10.2312/EUROVISSTAR.20141174 （ EG.org [2016年10月20日にアクセス]）。
  11. ↑ グラフ描画ソフトウェアライブラリ （ 記念 の オリジナル 2014年9月29日から インターネットアーカイブ ）） 情報： アーカイブリンクは自動的に使用されており、まだチェックされていません。指示に従ってオリジナルとアーカイブのリンクを確認してから、このメモを削除してください。 @初め @2 テンプレート：webachiv/iabot/www.yworks.com

K. M.ホール。 R次元二次配置アルゴリズム。 Manage Science、Seiten 219–229、1970。 ケネス・M・ホール： https://www.researchgate.net/publication/2274443571_an_r-dimensional_quadratic_placement_algorithm。 の： ResearchGate。 2021年4月13日にアクセス （英語）。

after-content-x4