% 4.3.5.1. トポロジカルソート
4.3.5.1. トポロジカルソート
トポロジカルソートは、
S_Cの中にあるクラスをCとしたとき、
Cではない他のクラスがR内で対応する要素に先行するものが無いような
クラスCを検索する処理によって行われます。
クラスCは結果の最初に配置されます。
S_CからCを削除し、
DがS_Cに含まれるもののとき(C,D)の全てのペアを削除します。
この処理を繰り返し、
結果の最後の、先行するものがないものとしてクラスを追加します。
先行するものを持たない要素が見つからなかったときに停止します。
もしS_Cが空でないときに処理が停止したら、集合Rには矛盾があります。
もし有限のクラスの集合である全てのクラスが
他のものによって先行されていたら、Rにはループが含まれています。
つまり、クラスC1,...,Cnの繋がりに対して、
CiがCi+1ただし1<=i<nに先行し、CnがC1に先行しています。
ときにはS_Cに先行するものがないクラスが存在することがあります。
このような場合は、これまでに計算されたクラス優先順位リストで
もっとも右にあるダイレクトスーパークラスを持つものを選択します
（そのような候補クラスがないときはRは部分順序を生成できず、
CがS_Cに含まれるときのR_Cは矛盾しています）。
より正確な言葉であらわすと、
{N1,...,Nm}, m>=2をS_Cに先行するものがないクラスとします。
(C1,...,Cn), n>=1をこれまでに構築したクラス優先順位リストとします。
C1はもっとも特定的なクラスであり、
Cnはもっとも特定的ではないクラスです。
ここで1<-j<=nのもっとも大きな数
1<=j<=nを、1<=i<=mでNiがCjのダイレクトスーパークラスである
iが存在するような最大の数とします。
このときNiは次に配置されるものになります。
先行するものがないクラスの集合から選択するというこのルールの効果は、
単純なスーパークラスのつながりであるクラスが
クラス優先順位リストで隣接しており、
相対的に分離した各サブグラフのクラスが
クラス優先順位リストで隣接するようになります。
例えば、T1とT2をクラスJのみを共通要素とするサブグラフとします。
JのスーパークラスはT1とT2のいずれにも現れず、
JはT1とT2の両方のクラスのスーパークラス内にあるとします。
T1の底をC1とし、
T2の底をC2とします。
あるクラスのダイレクトスーパークラスにC1,C2という順番で
現れているようなクラスをCとしたとき、
Cのクラス優先順位リストはCで始まり、
T1のJを除くすべてのクラスが続きます。
クラスT2のすべてのクラスが次に続きます。
クラスJとそのスーパークラスは最後に現れます。