大小を決めない組があってよい
半順序は、対象の集合に反射性・反対称性・推移性を満たす関係を与えたものです。反対称性は、aがb以下で、bもa以下ならaとbは同じ要素であるという条件です。対称性とは異なり、逆向きにも関係すれば同一だと制限します。一方、どの二要素も必ず比べられるという条件は要求しません。仕事の依存関係では、互いに関係しない二つの作業があっても自然です。どちらが先か決まっていないことと、どちらから始めても常に安全であることは同じではありません。資源の競合など、順序関係に入れていない条件も別に確認します。
包含関係を小さな集合で見る
集合の包含を使うと、半順序を手で確かめられます。空集合は{a}にも{b}にも含まれ、どちらも{a,b}に含まれます。しかし{a}は{b}に含まれず、その逆も成り立ちません。この二つは比較不能です。ここで要素数が同じだから同じ集合だと扱うと、包含という元の関係を変えてしまいます。大小を要素数だけで決めた順序と、各要素の所属を比較する包含関係は別です。反対称性は、A⊆BとB⊆Aの両方が成り立つならA=Bとなることから確認できます。推移性も、Aの各要素がB、さらにCへ含まれることを追えば示せます。
循環と自己関係を区別する
作業AがBの前提で、BがCの前提なら、AはCにも先行する必要があります。依存を推移的に広げた関係が順序になります。異なる作業AとBが互いを前提にする循環は、反対称性に反します。ただし反射的な半順序ではA≤Aを許すので、グラフ上の自己関係と異なる要素を回る循環は区別します。実装で通常使うDAGは自己ループを持たない厳密な依存を表すことが多く、半順序の反射的な関係をすべて辺として描くわけではありません。図の表し方と数学的な関係を混同しないことが大切です。
一つの並べ方に固定しすぎない
DAGのトポロジカル順序は、依存する辺の向きを守って全作業を一列へ並べるものです。Aの後にBとCが独立して続くなら、A,B,CとA,C,Bの両方が許されます。一つの並びを得たことから、BがCの前提だったと逆算してはいけません。アルゴリズムが同順位の候補をどの順に取り出すかでも出力は変わります。再現可能な表示が必要なら、候補の選択規則を追加できますが、それは元の依存を発見したこととは違います。どの並びでも同じ副作用になるかなど、実行時の正しさは順序制約のモデルと合わせて考えます。
極大と最大を読み分ける
極大要素は、それより真に大きい要素が存在しない要素です。最大要素は、すべての要素以上である要素です。包含で順序付けた集合族{{a},{b}}では、両方とも極大ですが、最大はありません。これに{a,b}を加えると、それが最大になります。日本語の「一番大きい」だけでは二つが混ざりやすいので、全要素と比較できる必要があるかを確かめます。同様に極小と最小も区別します。候補の一つがこれ以上改善できないという性質と、すべての候補より上であるという性質を分けることは、最適化や探索の結果を説明するときにも役立ちます。
包含の図を検算する
{a}から{a,b}へ進めても、{b}へ進めるとは限りません。図の上下や描画上の距離ではなく、関係の定義を使って判定します。推移的に導ける線を省いた図でも、元の関係からその到達を復元できます。表示する辺が少ないことと、比較可能な組が少ないことを混同しないようにします。