グラフ・レイアウト用語集

> >

数値

2 重接続グラフ: 2 接続グラフを参照してください。
2 接続グラフ: 「2 連結されたグラフ」とも呼ばれる。任意の 1 つのノードが削除されても、接続されたままのグラフになっている接続グラフ。 (つまり、少なくとも 2 つの異なるパスがすべての 2 ノード間に存在するグラフ。) 2 接続グラフには、 cut-edgeも切断ノードもない。

C

cut-edge: グラフからエッジを削除したときに、グラフの接続が解除される場合、このエッジは cut-edge です。次のグラフでは、ノード 3 とノード 5 の間のリンクは cut-edge です。そのエンドポイントは切断ノードであることに注意してください。

N

NP 完全: 効率的な解法アルゴリズムが発見されていない計算上の問題を表すクラス。多くのグラフ・レイアウトの問題も含め、多くの重要なコンピューター・サイエンス上の問題がこのクラスに属する。

あ

アスペクト比: 幅と高さの比率。正方形のアスペクト比は 1 である。
アニーリング: 「シミュレーテッド・アニーリング」を参照してください。

い

入れ子グラフ: グラフであるノードを含むグラフ、つまり入れ子になっているサブグラフを含むグラフ。
インクリメンタル・レイアウト: 変更を最小にするために、修正済みのグラフにレイアウト・アルゴリズムを 2 度目に適用する際の開始点として以前のレイアウトの結果を使用するレイアウト・プロセス。

え

エッジ: グラフ内の 2 つの頂点を結ぶ線。エッジは、「リンク」または「接続」とも呼ばれる。この文書では、「エッジ」という用語の代わりに、主に「リンク」という用語を使用します。

お

親ノード: 現行ノードに接続された、ルート・ノードに近い方のノード。ツリーでは、親ノードに付随するリンクは、親ノードの親ノードで終了するリンクを除き、すべて子ノードで終了する。
折れ線描画: 各リンクが多角形のチェーンとして描画されている図。

か

環状: 開始ノードと終了ノードが同じである、グラフのパス。「ループ」とも呼ばれる。
環状グラフ: 環状が含まれているグラフ。

き

兄弟ノード: 同じ親ノードを持つ子ノードは、兄弟ノードと呼ばれる。

く

クラスター: 一緒に近くに配置する必要があるノードのセット。環状レイアウトは、クラスターをリングまたはスター型に配置します。リングおよびスター型も参照。
クラスター間リンク: 終了ノードが別のクラスターにあるリンク。
クラスター内リンク: 終了ノードが同じクラスターにあるリンク。
グラフ: 有限のリンク (「エッジ」または「接続」とも呼ばれる) のセットで接続された有限のノード (「頂点」とも呼ばれる) のセット。
グラファー: ノードおよびリンクのコレクションを管理するために使用される Java™ オブジェクト。
グラフ間リンク: 入れ子グラフで、終了ノードが、異なるサブグラフに含まれているリンク。
グラフ・モデル: グラフ・レイアウトでは、適切な、グラフ用の汎用 API を定義する Java™ クラス。
グラフ・レイアウト: レイアウト・アルゴリズムをグラフに適用する処理。また、レイアウト処理により作成されたグラフ描画。
グリッド描画: ノードおよびリンクの曲折点が離散的な (整数の) 座標を持つ描画。

け

傾斜: 子ノードを水平方向または垂直方向に交互に配置する、ツリーの配置戦略。

こ

固定ノード: グラフ・レイアウトまたはリンク・レイアウト中に、位置が変わらないノード。ユーザーがノードを固定として指定すると、レイアウト・アルゴリズムはそのノードを移動できない。
固定リンク: グラフ・レイアウトまたはリンク・レイアウト中に、位置が変わらないリンク。ユーザーがリンクを固定として指定すると、レイアウト・アルゴリズムはそのリンクの形状を変更できない。
子ノード: 現行ノードに接続された、ルート・ノードから遠い方のノード。ツリーでは、親ノードに付随するリンクは、親ノードの親ノードで終了するリンクを除き、すべて子ノードで終了する。

さ

再帰: 大きい構造に適用するメカニズムと同じメカニズムをその副構造にも適用すること。入れ子グラフに適用される再帰レイアウトは、各サブグラフにも適用される。
サイクロマチック数: m がエッジの数で n がノードの数である場合に、m - n + 1 に等しい数。以下の図では、エッジの数が 10 でノードの数が 8 である。つまり、サイクロマチック数は 10 - 8 + 1 = 3 となる。
サブグラフ: 別のグラフに含まれるグラフ。フラット・グラフでは、G' のノードやリンクのセットが G のノードやリンクのセットに含まれている場合、G' は G のサブグラフである。

入れ子グラフでは、グラフであるノードが、入れ子グラフのサブグラフと呼ばれる。

し

自動レイアウト: ユーザーの介入なしにレイアウト・アルゴリズムがすべてを行うレイアウト・プロセス。
シミュレーテッド・アニーリング: 特定の目標に対して最適値にかなり近い値を見つけるための、温度スキームを用いた数学的手法。シミュレーテッド・アニーリングは、鋼鉄を熱して徐々に冷却する際の鋼鉄アニーリングの物理的作用から得た発想である。グラフ・レイアウトにおいて、シミュレーテッド・アニーリングは、ラベルを他のラベルもしくはノードやリンクと重ならないように配置するために使用される。
出発リンク: ノードで開始する方向リンク。
シード値: ランダム数ジェネレーターの初期化で使用される値。一部のレイアウト・アルゴリズムは、レイアウト計算で乱数を使用する。

す

スター型: ノードが環状に配置され、各ノードが中心ノードに接続されているネットワーク・トポロジーの種類。
スパンニング・ツリー: 以下のように定義される最小のサブグラフ。フラット・グラフ G のスパンニング・ツリー S が、グラフのすべてのノードを含む G のサブグラフであり、そのリンクが、グラフのリンクのサブセットである。S 内に存在しない G のリンクの数は、S 内に閉路がないことを実現する最小数である必要があります。次の図に、スパンニング・ツリーを赤色のリンクで示します。
スプライン: ノードを接続しているリンクの表示形式の 1 つ。制御点によって制御される滑らかな曲線。

せ

制約: オブジェクトを配置できる領域を制限する指定。例えば、「オブジェクトを別のオブジェクトの左側に配置しなければならない」という制約など。
接続: グラフのエッジの別名。エッジも参照。
接続グラフ: それぞれのノードのペアを接続するパスがあるグラフ。非接続グラフも参照。
接続コンポーネント: 接続されたグラフやサブグラフ。フラット・グラフ G の接続コンポーネントは、G の最大接続サブグラフになる。
切断ノード: あるノードをグラフから削除するとグラフが接続グラフでなくなってしまう場合、そのノードは切断ノードである。以下のグラフで、ノード 5 は切断ノードである。
セルフリンク: ソース・ノードと宛先ノードが同じノードであるリンク。

ち

力指向レイアウト: 引き付けたり、反発したりする一連の力に従ったノード位置の反復計算に基づいて、無向グラフの直線描画を作成するためのレイアウト・アルゴリズムのクラス。このような力は、リンク交差がほんのわずかしかないか、まったくないレイアウトが作成されるように計算される。
頂点: エッジにより接続できるグラフのエレメント。頂点は「ノード」とも呼ばれる。この文書では、「頂点」という用語の代わりに、主に「ノード」という用語を使用する。グラフは、有限のエッジ (「リンク」または「接続」とも呼ばれる) のセットによって接続された有限の頂点のセットからなる。描画では多くの場合、頂点はボックスとして、エッジは線として表示される。
直線: 各リンクが直線セグメントとして描かれている描画。
直交描画: 各リンクが水平セグメントおよび垂直セグメントを交互につないだ多角形のチェーンとして描画されている図。

つ

ツリー: 無向ツリーは、連結した無向非環状グラフ (閉路を含まないグラフ) です。有向ツリーは、各ノードが入リンクを 1 つしか持たない連結した有向グラフです (到着リンクを持たないルート・ノードを除く)。

と

度合い: グラフ G のノード v の度合いは、v に接触するグラフのエッジの数である。
到着リンク: ノードで終了する方向リンク。
トポロジー: グラフの構造。ノードを移動しリンクの形状変更をすることにより他から描画を取得できる場合、作成された 2 つのグラフは同じトポロジーを持つ。

の

ノード: グラフの頂点の別名。この文書では、「頂点」という用語の代わりに、主に「ノード」という用語を使用する。

は

パス: グラフのリンクを使用して、あるノードから別のノードに導く連続したノードのつながり。これは、グラフ内のノードを通るリンクに沿った経路である。パスの長さは、その上を移動するリンクの数である。
バス・トポロジー: 一連のノードがバス・オブジェクトに接続されているネットワーク・トポロジーのタイプ。
半自動レイアウト: ユーザーが自動レイアウト・プロセスの結果を手動により改良するレイアウト・プロセス。

ひ

非環状グラフ: 環状がないグラフ。
非接続グラフ: パスでリンクされていない少なくとも 2 個のノードを含むグラフ。次のグラフでは、ノード 5 は、パスで他のノードにリンクされていません。ノード 3 および 4 は、ノード 3 および 4 以外のノードにパスでリンクされていません。
非平面グラフ: リンクを他のリンクに交差することなく描画できないグラフ。
非方向リンク: 特定の方向を持たないリンク。方向リンクと異なり、非方向リンクには付随ノード間の順序付けがない。数学的な意味では、方向リンクが順序付けられているノード・ペアであるのに対して、非方向リンクは順序付けされていないノード・ペアである。方向リンクおよび無向グラフも参照。

ふ

複数リンク: 同じソース・ノードと宛先ノードの間にある複数のリンク。
付随: リンク - ノード接続。ノードがリンクの端にある場合、そのリンクはそのノードに付随している。リンクがノードに付随している場合、そのノードはそのリンクに付随している。
フラット・グラフ: 入れ子グラフの逆。含まれているノード自体がグラフではないグラフ。入れ子グラフを参照。
分岐: それ自体がツリーであるツリーのサブパーツ。

へ

平面グラフ: リンクを他のリンクに交差させずに描画できるグラフ。
辺の交差: リンク交差を参照してください。

ほ

方向リンク: リンクの付随ノードで始まり、他の付随ノードで終わる方向付きのリンク。方向リンクには、通常、方向を示す矢印が描かれている。数学的な意味では、非方向リンクが順序付けされていないノード・ペアであるのに対して、方向リンクは順序付けられているノード・ペアである。有向グラフも参照。
放射描画: ノードがルート・ノードの周りに放射状に配置されるレイアウト・スタイル。

む

無向グラフ: すべてのリンクが、順序付けられていないノード・ペアに関連付けられているグラフ。非方向リンクも参照。

ゆ

有向グラフ: すべてのエッジが、順序付けられたノードの対に関連付けられているグラフ。有向グラフとも呼ばれる。関連項目: 方向リンク
優先レイアウト: 再帰レイアウトでは、各グラフに使用されるように設定されるレイアウト・インスタンス。グラフのプロパティーに保管される。

り

リンク: グラフ内のエッジの別名。この文書では、「エッジ」という用語の代わりに、主に「リンク」という用語を使用する。エッジも参照。
リング: ノードが環状構成で配置されるネットワーク・トポロジーの種類。
リンク交差: リンク交差は、付随ノード以外の場所でリンクが交差する場合に発生する。「エッジ交差」とも呼ばれる。多くの場合、リンク交差の数を最小にするためにレイアウト・アルゴリズムが使用される。
リンク・バンドル: 一連の平行線として描画された、グラフ内の所定のノード・ペアを接続する一連のリンク (エッジ)。複数リンクを参照。
隣接ノード: 所定のノードにリンクで接続されているノード。
リーフ: ルートではなく、最大で 1 つの付随エッジを持つ、ツリー内のノード。すなわち、子ノードを持たないノード。ツリーのノードには、ルート (1 つの特別なノード)、リーフ、および内部ノード (ルートでもリーフでもないすべてのノード) がある。
リーフ再帰ツリー: ツリーで、ツリーのリーフのみがサブグラフになる入れ子グラフ。

る

ルート: ツリーでは、ルートとは、特定の唯一のノードのこと。有向グラフでは、ルートとは、到着リンクがないノードのこと。

れ

レイアウト・アルゴリズム: 適切なグラフ表示にするために、ノードの新しい座標およびリンクの新しい形状、またはそのいずれかを計算するプロセス。
レイアウト領域: グラフ・レイアウトでは、グラフがレイアウトされる際にグラフ描画が配置される矩形。