状態遷移図を対象としたグラフの階層的描画の実装を目的とした教科書のメモ。
アルゴリズムの適用前に自己ループエッジを取りのぞき、多重エッジをまとめる。
頂点の線形順序が与えられたら、エッジ集合をふたつの部分集合に分割できる。 \(\mathrm{order}(v)\)が与えられているとき、エッジ集合\(E\)の要素\(e = (u, v)\)について、\(\mathrm{order}(u) \lt \mathrm{order}(v)\)を満たす集合と満たさない集合に分割する。 ふたつの部分集合はどちらもFSである。
Coffman-Grahamアルゴリズムはふたつのステップからなる。 最初のステップで\(G\)の全頂点に一意なラベル\(\lambda : V \to \mathbb{N}\)を計算する。 第二ステップで頂点を階層に配置する際、ラベルを優先順位として用いる。 最初のステップのラベルの計算は、下記に定義される頂点集合同士の比較を伴う。 下記が成り立つとき、ふたつの頂点集合\(U_1\)と\(U_2\)は\(U_1 \lt U_2\)である。
第二ステップで、下層から上層に向かって各頂点に階層を配置する。 このとき、階層内の頂点数を上限\(W\)以内に保つ。
\(G\)のトポロジカルな順序付けを構築する。 頂点を、それらの入力近傍の位置集合について辞書順に並べる。 このような順序付けを行うためには、 次の条件を満たす頂点\(v\)を択び、ひとつずつ頂点を順序に加える。 まず、\(v\)の入力近傍がすべて既に半順序に加えられていること。 このような頂点の候補は複数存在しえるので、それらの入力近傍で一番最近追加された入力近傍がもっともearlierであること。 ふたつの頂点の候補が同じ入力近傍を共有している場合、二番めに最近追加された入力近傍がearlierであるほうを択ぶ。 以下、この条件を続ける。
ダミー頂点を少なくすることを目的とする。ダミー頂点が少なければ、エッジは短く保たれる。
関数\(\mathrm{PromoteVertex}(v)\)は、\(v\)の入力頂点のなかで、一階層上に位置する頂点\(u\)の\(\mathrm{PromoteVertex}(u)\)を積算する。 これに\(v\)の出力次数と入力次数の差を加えた値を返す。 また、\(v\)の階層をひとつ上に移動する。
頂点の格上げヒューリスティクスでは、ランク移動が発生しなくなるまで、すべての頂点\(v \in V\)について、次に述べる操作をくりかえす。 \(v\)の入力次数が\(0\)でなければ、\(\mathrm{PromoteVertex}(v)\)を行う。 ただし、結果が正の場合、移動は発生しなかったものとする。
初期ランクは厳密にはLongest-Pathアルゴリズムで求めていないように見える。 トポロジカルな順序に従って、ランクを割り振っていく。 その後、短くすることが可能なエッジを短くする。
全域木はソースから開始したほうがよいのか？
エッジの重みが\(1\)である場合のカット値の計算を考える。 ツリーエッジの向きと、対応するグラフエッジの向きが逆転している場合、末尾要素と先頭要素が入れ替わるので、カット値の符号を反転させる。 エッジ\(e\)について、ツリーエッジの向きとグラフエッジの向きが同じ場合は\(+1\)を、向きが逆転している場合は\(-1\)を与えるような変数を\(R_e\)で表すとする。
頂点\(x\)について、非ツリーエッジだけを考慮した入力次数と出力次数の差を\(d_x\)で表すとする。 全域木のツリーエッジ\((u, v)\)の端点\(v\)が葉であるとき、カット値は、 \begin{align} C_{(u, v)} &=R_{(u, v)} (d_v + R_{(u, v)}) \\ &=R_{(u, v)} d_v + 1 \end{align} と表せる。 \((u, v)\)以外の\(v\)の全近接エッジが非ツリーエッジであるため、ここで、\(d_v + R_{(u, v)}\)は入力次数と出力次数の差に等しい。
あるツリーエッジ\((u, v)\)について、端点\(v\)が子ツリーエッジ\((v, w_i)\)を持つとき、 \[ D_v = d_v + \sum_i D_{w_i} \] を定義する。\(D_v\)は端点\(v\)側の要素に対して、入力する非ツリーエッジの数と出力する非ツリーエッジの差である。 このような値は、全域木を子から走査しながら積算することで容易に求まる。 このとき、ツリーエッジ\((u, v)\)のカット値は、 \begin{align} C_{(u, v)} &=& R_{(u, v)} (D_v + R_{(u, v)}) \\ &=& R_{(u, v)} D_v + 1 \end{align}
あるツリーエッジ\((u_1, v_1)\)を全域木から除去し、新しいツリーエッジ\((u_2, v_2)\)を加えたとき、\(d_{v_1}\)と\(d_{v_2}\)が更新される（インクリメントまたはデクリメントする）。 全域木上で\(v_1, v_2\)自体とその祖先の頂点\(\{x\}\)について、\(D_x\)を更新する。
\(u, v \in V_2\)で、\(u\)が\(v\)の左にあるとき、\(u, v\)に接続するエッジの交差数を\(c_{uv}\)とする。 交差数行列は\(c_{uv}\)を要素に持つ。 \(V_1\)の頂点は固定されていると仮定するので、この行列はOLCMだけに関係する。
\(\delta_{ij}^k\)を、階層\(k = 1, 2\)上の頂点\(i, j\)の順序を表すような0-1変数とする。 この変数から、最小化の目的関数となるような順列\(\pi_i\)のペアの交差数の式を導出する。 つまり、\(\pi_k(i) \lt \pi_k(j)\)ならば\(\delta_{ij}^k = 1\)、そうでなければ\(0\)。 \(\delta_{ij} = 1 - \delta_{ji}\)であることは明らかである。 \[ \mathrm{C}(\pi_1, \pi_2) = \sum_{i=1}^{n_2-1} \sum_{j=i+1}^{n_2} \sum_{k\in\mathrm{N}(i)} \sum_{l\in\mathrm{N}(j)} \delta_{kl}^1 \delta_{ji}^2 + \delta_{lk}^1 \delta_{ij}^2 \] OLCMの場合、\(\pi_1\)が固定されていると仮定し、交差を最小化するような\(V_2\)の順序\(\pi_2\)を探す。 つまり、下記を最小化したい。 \[ \mathrm{C}(\pi_2) = \sum_{i=1}^{n_2-1} \sum_{j=i+1}^{n_2} \sum_{k\in\mathrm{N}(i)} \sum_{l\in\mathrm{N}(j)} \delta_{kl}^1 \delta_{ji}^2 + \delta_{lk}^1 \delta_{ij}^2 \] この\(\mathrm{C}(\pi_2)\)は二次項を含むので解くのが難しい。 しかし、\(V_2\)の頂点\(i\)と\(j\)のペアの交差数 \[ c_{ij} = \sum_{k\in\mathrm{N}(i)} \sum_{l\in\mathrm{N}(j)} \delta_{lk}^1 \] を用いて、 \begin{align} \mathrm{C}(\pi_2) &= \sum_{i=1}^{n_2-1} \sum_{j=i+1}^{n_2} c_{ji} \delta_{ji}^2 + c_{ij} \delta_{ij}^2 \\ &= \sum_{i=1}^{n_2-1} \sum_{j=i+1}^{n_2} c_{ji} (1 - \delta_{ij}^2) + c_{ij} \delta_{ij}^2 \\ &= \sum_{i=1}^{n_2-1} \sum_{j=i+1}^{n_2} (c_{ij} - c_{ji}) \delta_{ij}^2 + c_{ji} \\ &= \sum_{i=1}^{n_2-1} \sum_{j=i+1}^{n_2} (c_{ij} - c_{ji}) \delta_{ij}^2 + \sum_{i=1}^{n_2-1} \sum_{j=i+1}^{n_2} c_{ji} \end{align} のように書きなおすことができる。 こうして問題は、頂点を順序づけるようなベクトル\(\delta^2 \in \{0, 1\}^{\begin{pmatrix} n_2 \\ n \end{pmatrix}}\)を探すことに帰着した。 一貫した順序を頂点に与えるために、「3-cycle」制約を強制する。 これは、頂点\(i\)の優先度が頂点\(j\)より高く、頂点\(j\)の優先度が頂点\(k\)より高ければ、頂点\(i\)は頂点\(k\)に優先しなければならないという制約である。
\(c_{ij}\)と\(c_{ji}\)は前もって決定することができ、\(\sum_{i=1}^{n_2-1} \sum_{j=i+1}^{n_2} c_{ji}\)は定数なので、問題は下記のように線形計画として書くことができる。 ここで、\(\delta_{ij}^2\)はより一般的な\(x_{ij}\)で置きかえる。
\[ \sum_{i=1}^{n_2} \sum_{j=i+1}^{n_2} a_{ij} x_{ij} \text{を最小化する。} \] ただし、 \begin{align} & 0 \le x_{ij} + x_{jk} - x_{ik} \le 1 & 1 \le i \lt j \lt k \le n_2 \\ & 0 \le x_{ij} \le 1 & 1 \le i \lt j \le n_2 \\ & x_{ij} \text{は整数} \end{align}
ダミー頂点間のsegmentをinner segmentsと呼ぶ。