描画アルゴリズムの入力は属性付きグラフ\(G = (V, E)\)で、ループや多重エッジを含むかもしれない。 \(G\)は連結されていると仮定する。各連結成分は独立して配置することができる。
アルゴリズムは、中心点\((x(v), y(v))\)を持つ平面上の矩形を各ノード\(v\)に割りあて、Bスプライン制御点列\((x_0(e), y_0(e)), \dots, (x_n(e), y_n(e))\)を各エッジ\(e\)に割りあてる。
タイムラインを持つようなグラフの描画や、送受信ノードが目だつように、ユーザはレイアウトをさらに制約できる。 次節に述べるアルゴリズムの最初のパスは、離散ランク\(0 \dots \mathrm{Max\_rank}\)をノードに割りあてる。 同じランクのノードは同じ\(Y\)座標値を与えられる。 ユーザは\(V\)の部分集合に対して、集合\(S_{\max}, S_{\min}, S_0, S_1, \dots, S_k\) を与えてもよい。 これらは、最大、最小、同ランクでいっしょに配置されるべきノードの集合である。
最初のパスでエッジに合わせて\(G\)の各ノード\(v\)に整数ランク\(\lambda(v)\)を割りあてる。 エッジ\(e = (v, w)\)の長さ\(l(e)\)を\(\lambda(w) - \lambda(v)\)と定義するとき、\(E\)の全\(e = (v, w)\)について\(l(e) \ge \delta(e)\)が成りたつ。 ここで\(\delta(e)\)はある所与の最小長制約を表現する。 \(\delta(e)\)は通常\(1\)だが、任意の非負の整数値をとることができる。 \(\delta(e)\)は後に述べる技術的な理由で内部的に設定されるかもしれないし、ユーザがランク割りあてを調整する際に設定されるかもしれない。 このパスでは、空でない集合\(S_{\max}, S_{\min}, S_0, \dots, S_k\)が一時的にひとつのノードにマージされる。 ループは無視され、多重エッジは合計された重みを持つひとつのエッジにマージされる。 葉のランクは最適ランキングによって自明に決定されるので、効率のために上記の集合のどれにも含まれない葉ノードは無視される。
原則A3はエッジを短くする。 よりよいレイアウトの作成に加えて、短いエッジは全エッジの合計長に依存する後続のパスの実行時間を短くする。 すべての重みづけされたエッジ長の合計を最小化するような最適ランキングを見つけることが望ましい。
最適ランキングの探索は下記の整数計画に再公式化される。
\[ \min \sum_{(v, w) \, \mathrm{member} \, E} \omega(v, w) (\lambda(w) - \lambda(v)) \\ \text{subject to:} \, \lambda(w) - \lambda(v) \ge \delta(v,w) \, \forall \, (v,w) \, \mathrm{member} \, E \]
既に述べたように、重み付け関数\(\omega\)と最小長関数\(\delta\)は、エッジ集合\(E\)にひもづけられた非負の有理数と非負の整数である。
ネットワークシンプレックス法にもとづく単純な問題へのアプローチを示す。 時間複雑性が多項式時間であることは証明されていないが、実際には、わずかの反復だけで高速に動作する。
いくつかの定義と観察から始める。 可能なランキングはすべての\(e\)について長さの制約\(l(e) \ge \delta(e)\)を満たす。 必ずしも可能ではない任意のランキングが与えられたとき、エッジのスラックは長さと最小長の差である。 つまり、すべてのエッジのスラックが非負であるならば、可能なランキングである。 スラックがゼロならば、そのエッジはタイトである。
グラフの全域木はランキングを導く。 厳密にいえば、ランキングと等価なファミリを導く。 全域木は根を持たない無向グラフに内在していて、有向木である必要はない。 初期ノードを択んでランクを割り当てることでランキングを生成する。 ランクを割り当てられたノードの全域木上の近接ノードごとに、接続エッジの最小長によってランクを加算または減算して割り当てる。 増減は接続エッジの先頭か末尾かによる。 この処理はすべてのノードがランクづけされるまで続ける。 可能なランキングを導くならば、全域木は可能である。
可能な全域木が与えられたら、次に述べるように整数のカット値を各ツリーエッジに関連づける。 ツリーエッジが削除されたら、エッジの末尾ノードを含む末尾要素と先頭ノードを含む先頭要素のふたつの連結要素に木が分解される。 末尾要素から先頭要素への全エッジの重みの総和から、先頭要素から末尾要素への全エッジ（削除したエッジを含む）の重みの総和を引いたものとカット値は定義される。
典型的には（縮退の場合はあてはまらない）、負のカット値は、先頭要素から末尾要素へのどれかのエッジがタイトになるまで、可能な限りツリーエッジを伸延することで、重みづけされたエッジの長さの合計を減らせることを示している。 これは、全域木のツリーエッジを新しいタイトエッジで置き換えると新しい可能な全域木が得られることと対応している。 最適なランキングを用いて、可能な全域木から別の最適なランキングを生成できることは明らかである。 この観察が、代数的な文脈ではなくグラフィカルな文脈でランキング問題を解くための鍵になる。 負のカット値を持つツリーエッジは、すべてのツリーエッジが非負のカット値を持つようになるまで、適切な非ツリーエッジで置き換える。 終了が保証できるように非循環テクニックを採用するべきだが、実際にはその必要は見つからなかった。 結果の全域木は最適なランキングに対応する。
procedure rank()
feasible_tree();
while (e = leave_edge()) != nil do
f = enter_edge(e);
exchange(e, v);
end
normalize();
balance();
end
feasible_treeは初期の可能な全域木を構築する。
この手続きは後により完全に記述する。
シンプレックス法はこの可能解から開始して不変量を維持する。
leave_edgeは負のカット値を持つツリーエッジを返す。
負のカット値を持つツリーエッジがなければnilを返す。
このとき解は最適である。
負のカット値を持つどのようなエッジも除去するために択ばれうる。
enter_edgeはeを置き換えるための非ツリーエッジを返す。
エッジeを分解する。
つまり、木を先頭要素と末尾要素に分解する。
先頭要素から末尾要素へのすべてのエッジを考慮し、最小スラックを持つエッジを択ぶ。
これは可能であるように維持するために必要である。
procedure feasible_tree()
init_rank();
while tight_tree() < |V| do
e = スラックの最小量で木に接続する非ツリーエッジ;
delta = slack(e);
if 接続ノードがe.head then delta = -delta;
for v in Tree do v.rank = v.rank + delta;
end
init_cutvalues();
end
init_rankはここでは与えない。
我々のバージョンはノードをキューに保持する。
未走査の入力エッジを持たないノードがキューに入っている。
ノードをキューから取り出して、その入力エッジの条件を満たす最小ランクを割りあて、出力エッジに走査済みというマークをつける。
単純な場合、つまり、すべてのエッジについて\(\delta = 1\)の場合、グラフを半順序集合として、最小要素にランク0を設定することに対応する。
これらのノードを半順序集合から取りのぞき、新しい集合の最小要素にランク1を設定し、と繰り返す。
tight_treeは、ある固定ノードを含むタイトエッジの最大の木を探し、その木のノード数を返す。
そのような最大の木は、タイトエッジだけを用いた無向グラフ内の固定ノードから到達可能なすべてのノードからなるサブグラフの全域木である。
特に、すべてのそのような木は同じ数のノードを持つ。
init_cutvaluesはツリーエッジのカット値を計算する。
各ツリーエッジについて、ノードが先頭要素と末尾要素のどちらに属しているかマークする。
次に、先頭要素と末尾要素が異なるすべてのエッジの符号付き重みの和を計算する。
先頭要素から末尾要素に向かうエッジについて、符号は負になる。
このコストを減らすために、可能な木の葉から内側に向かう方向に探索している場合、エッジに局所的な情報を用いてカット値を計算できることを示す。 エッジの端点がその木の葉であれば、先頭要素か末尾要素がひとつのノードからなるので、ツリーエッジのカット値の計算は自明である。 ひとつのエッジを除いて、ノードに接続するすべてのエッジのカット値が分かっているとする。 残るエッジのカット値は、既知のカット値の合計に、与えられたノードに接続するエッジにのみ依存する項を加えたものである。
既知のカット値を持つふたつのエッジに、図示した方向の三番めのエッジをつなぐ場合の計算を図2-4に示す。 他の場合も同様に扱える。 \((u, w)\)と\((v, w)\)のカット値がわかっていると仮定する。 大文字でラベル付けしたエッジは所与の方向のすべての非ツリーエッジを表現する。 これらの非ツリーエッジの先頭と末尾を要素によって示している。 \((u, w)\)と\((v, w)\)のカット値は、 \begin{align} c_{(u, w)} &= \omega(u,w) + A + C + F - B - E - D \\ c_{(v, w)} &= \omega(v,w) + L + I + D - K - J - C \end{align} \((w,x)\)のカット値は、 \begin{align} c_{(w, x)} &= \omega(w,x) + G - H + A - B + L - K \\ &= \omega(w,x) + G - H + (c_{(u, w)} - \omega(u, w) - C - F + E + D) + (c_{(v, w)} - \omega(v, w) - I - D + J + C) \\ &= \omega(w,x) + G - H + c_{(u, w)} - \omega(u, w) + c_{(v, w)} - \omega(v, w) - F + E - I + J \end{align}
別の価値ある最適化は、逆順に木を横断することである。 ある固定されたノード\(v_{\mathrm{root}}\)から開始して、各ノード\(v\)を逆順で横断する番号\(\mathrm{lim}(v)\)と子孫の最小番号\(\mathrm{low}(v)\)とそのノードが到達した\(\mathrm{parent}(v)\)でラベル付けする。
ノードがツリーエッジの先頭要素と末尾要素のどちらにあるか、つまり、非ツリーエッジが2要素間で交差しているかを調べる安価な方法を提供する。 \(e=(u, v)\)がツリーエッジで\(v_{\mathrm{root}}\)がそのエッジの先頭要素に含まれるとき（つまり、\(\mathrm{lim}(u) \lt \mathrm{lim}(v)\)）、\(\mathrm{low}(u) \le \mathrm{lim}(w) \le \mathrm{lim}(u)\)かつその場合に限り、ノード\(w\)は\(e\)の末尾要素に属する。 これの数はネットワークシンプレックス法の繰り返し中に効果的に木を更新するためにも使える。 \(f=(w, x)\)が入力エッジならば、カット値を調整しなければならないエッジは、木のなかで\(w\)と\(x\)を接続するパスにあるものだけである。 このパスは、\(w\)と\(x\)から最小の共通祖先ノード、つまり、\(\mathrm{low}(l) \le \mathrm{lim}(w), \mathrm{lim}(x) \le \mathrm{lim}(l)\)であるような最初のノードに到達するまで親エッジをたどることで決まる。 もちろん、これらの逆順のパラメーターは木のエッジを交換するときは調整しなければならないが、\(l\)配下のノードについてだけである。
ネットワークシンプレックスは置き換える負エッジの選択に非常に敏感である。 ツリーエッジのリストを毎回最初から探索するかわりに、すべてのツリーエッジを循環的に探索することで繰り返し回数を抑えられることを発見した。
頂点重みづけによる手法として重心法 (the median function) と中央値法 (the median function) が有名である。 頂点\(v\)について、隣接するランクの接続頂点の位置のリストを\(P\)とする。 近接ノードの位置は、現在の順序における序数で表される。 重心法では、\(P\)の要素の平均を\(v\)の重みと定義する。 中央値法では、\(P\)の要素の中央値を\(v\)の重みと定義する。 \(P\)の要素数が偶数である場合、中央値は2個存在する。 そのため、常に左の中央値を用いるか、常に右の中央値を用いるかの2個の中央値法が存在しうる。 中央値法は重心法よりも常に良い結果になる。 二階層グラフにおいて中央値法の結果は最小交差数の三倍以上にならないとEadesとWolmaldが示したように、若干理論的に有利である。 重心法はこのような下限を持たない。
ランクの割りあての後、1ランクよりも離れたノード間のエッジは、一時的または仮想ノード間の単位長エッジの連鎖に置き換えられる。 仮想ノードは中間ランクに配置され、元のグラフを近接するランクのノードだけに接続するエッジを持つグラフに変換する。 このパスでは自己エッジは無視され、多重エッジは前パスと同様にマージされる。
procedure ordeing()
order = init_order();
best = order;
for i = 0 to Max_iteartions do
wmedian(order, i);
transpose(order);
if crossing(order) < crossing(best) then
best = order;
end
return best;
end
Max_iterationsは繰り返しの最大回数である。
我々はMax_iterationsを24とした。
それぞれの繰り返しで、交差数が改善されれば新しい順序が保存される。
実際の実装では、最後の何回かの繰り返しが解を数パーセントしか改良しなくなるまで繰り返すような適応戦略が好ましいかもしれない。
wmedianは、重みづけ中央値ヒューリスティクスに基づき、それぞれのランク内で並びかえる。
transposeは、交差数が減少するならば、同じランクの近接する頂点を繰り返し交換する。
procedure wmedian(order, iter)
if iter mod 2 == 0 then
for r = 1 to Max_rank do
for v in order[r] do
median[v] = median_value(v, r - 1);
sort(order[r], median);
end
else ...
endif
end
procedure median_value(v, adj_rank)
P = adj_position(v, adj_rank);
m = |P| / 2;
if |P| == 0 then
return -1.0;
elseif |P| mod 2 == 1 then
return P[m];
elseif |P| == 2 then
return (P[0] + P[1]) / 2;
else
left = P[m - 1] - P[0];
right = P[|P| - 1] - P[m]
return (P[m - 1] * right + P[m] * left) / (left + right)
endif
end
procedure transpose(rank)
improved = True;
while improved do
improved = False;
for r = 0 to Max_rank do
for i = 0 to |rank[r]| - 2 do
v = rank[r][i];
w = rank[r][i + 1];
if crossing(v, w) > crossing(w, v) then
improved = True;
exchange(rank[r][i], rank[r][i + 1]);
endif
end
end
end
end
ordering関数内のループと同様、交差数が十分に小さく改善されたらループを打ち切る適応戦略が適用できる。
crossing(v, w)関数は、単純に\(v\)がランク内で\(w\)の左に現れた場合のエッジの交差数を数える。