HL アルゴリズム

HL アルゴリズムの要旨

このアルゴリズムは以下の 4 つのステップで機能します。
ステップ 1: レベル付け
ノードはグループに分割されます。 各ノード・グループはレベルを形成します。この目的は、インデックスが小さいレベルからインデックスが大きいレベルにリンクが常に向かうように、ノードをグループ化することです。
ステップ 2: 交差低減
ノードは各レベル内でソートされます。 アルゴリズムは、各レベルで、ノードが線上にこの順序で配置されるときに、リンク交差数を少なく抑えようとします (レベル・インデックスおよび位置インデックスを参照)。 この順序付けの結果、レベル内の各ノードの相対位置インデックスが作成されます。
ステップ 3: ノードの位置付け
レベル・インデックスおよび位置インデックスから、ノードのバランスの取れた座標が計算されます。 例えば、リンク方向が上から下のレイアウトでは、ノードは水平線に沿って配置され、同じレベルに属するすべてのノードの Y 座標が (ほぼ) 同じになります。 インデックスが小さいレベルのノードの Y 座標は、インデックスが大きいレベルのノードよりも小さくなります。 レベル内では、位置インデックスの小さなノードの X 座標は、位置インデックスの大きなノードよりも小さくなります。
ステップ 4: リンクの経路指定
リンクの形状は、リンクがレベル線でノードをバイパスするように計算されます。 多くの場合、これには、リンクがレベル線を交差する必要が生じるごとに曲折点を作成する必要があります。 上から下へ向かうレイアウトでは、こうした曲折点の Y 座標は、交差するレベル線と同じになります。(このような曲折点も位置インデックスを取得します)。
レベル・インデックスおよび位置インデックスに、どのように階層型レイアウト・アルゴリズムがレベル・インデックスおよび位置インデックスを使用してグラフを描画するかを示します。
階層型レイアウトにおけるレベル・インデックスおよび位置インデックスを示したダイアグラム
レベル・インデックスおよび位置インデックス
レイアウト・アルゴリズムのステップ用のパラメーターをいくつかの方法で設定できます。 例えば、ステップ 1 でノードに対してアルゴリズムが選択する必要があるレベル・インデックスを指定したり、ステップ 2 でレベル内の相対ノード位置を指定したりすることができます。 また、レベル内のノードの位置揃えおよびリンク形状のスタイルを指定することもできます。

HL の例

以下のコード・サンプルでは、階層型レイアウトの実行方法を示します。
var layout = new ibm_ilog.graphlayout.hierarchical.HierarchicalLayout();
graph.setNodeLayout(layout);
graph.performGraphLayout();