コフマン・グラハムアルゴリズム

コフマン・グラハムアルゴリズムは、半順序集合の要素をレベルのシーケンスに配置するアルゴリズムです。このアルゴリズムは、順序において次の要素が別の要素の後に来る場合、その要素はより低いレベルに割り当てられ、各レベルの要素数が固定幅Wを超えないように配置を選択します。W = 2の場合、可能な限り少ない数の異なるレベルを使用し、一般に、必要なレベル数の2 − 2 / W倍以下のレベルを使用します。

このアルゴリズムは、1972年にジョブショップスケジューリングへの応用を目的として発表したエドワード・G・コフマン・ジュニアとロナルド・グラハムにちなんで名付けられました。この応用では、順序付けの対象となる要素はジョブであり、境界Wは一度にスケジュールできるジョブの数、部分順序はジョブ間の前提条件関係を表します。目標は、すべてのジョブを最小の総時間で完了するスケジュールを見つけることです。その後、同じアルゴリズムはグラフ描画にも使用され、有向グラフの頂点を固定幅の層に配置して、ほとんどまたはすべてのエッジが一貫して下向きになるようにする方法として用いられています。

推移的還元（被覆関係）によって与えられる部分順序の場合、コフマン・グラハムアルゴリズムは、分割細分化データ構造をサブルーチンとして使用することで線形時間で実装できる。推移的還元が与えられていない場合は、それを構築するのに多項式時間を要する。

コフマン・グラハム アルゴリズムで解決されるジョブ ショップ スケジューリング問題のバージョンでは、n個のジョブJ ₁、J ₂、 ...、J _nの集合と、ジョブ J i がジョブ J j の開始前に完了しなければならないという先行制約 J i < J j のシステムが_与えられ_ます。各_ジョブは完了_までに単位時間かかると仮定します。スケジューリング タスクは、これらの各ジョブをW個の同一プロセッサのシステム上のタイム スロットに割り当て、割り当てのメイク スパン(最初のジョブの開始から最後のジョブの完了までの時間) を最小化することです。抽象的には、先行制約はジョブの半順序を定義するため、この問題は、先行制約を尊重しながら、各タイム スロットにプロセッサ数と同じ数のジョブ (レベルあたり最大W個の要素) が含まれるように、この半順序の要素をレベル (タイム スロット) に割り当てる問題として言い換えることができます。このアプリケーションが、コフマンとグラハムがアルゴリズムを開発した当初の動機でした。^{[ 1 ] [ 2 ]}

杉山、田川、戸田（1981）^{[ 3 ]}によって概説された階層型グラフ描画フレームワークでは、入力は有向グラフであり、グラフの描画はいくつかの段階で構築されます。^{[ 4 ] [ 5 ]}

1. フィードバックアークセットを選択し、そのセットのエッジを反転させることで、入力を（可能であれば）反転エッジが少ない有向非巡回グラフに変換する。
2. グラフの頂点には整数y座標が割り当てられ、各辺について、始点となる頂点の座標が終点となる頂点の座標よりも高くなり、かつ同じy座標を持つ頂点は最大でW個となるように設定されます。このようにして、有向非巡回グラフのすべての辺と、元のグラフのほとんどの辺は、一貫して下向きになります。
3. 各辺の中にダミー頂点を導入することで、分割された辺はすべて、図面の隣接するレベルにある頂点のペア同士を接続するようにする。
4. y座標が同じ頂点のグループごとに、結果として得られる図における交差の数を最小限に抑えるように頂点の順列が行われ、この順列に従って頂点にx座標が割り当てられます。
5. グラフの頂点と辺は、それぞれに割り当てられた座標とともに描画されます。

このフレームワークでは、y座標の割り当ては、部分的に順序付けられた集合 (頂点集合に到達可能性順序付けされたグラフの頂点) の要素をレイヤー (同じy座標を持つ頂点の集合) にグループ化することを含み、これは Coffman–Graham アルゴリズムによって解決される問題です。^{[ 4 ]}レイヤー化ステップには Coffman–Graham アルゴリズム以外の代替アプローチが存在しますが、これらの代替アプローチは一般的に、レベルの最大幅の制限を組み込むことができないか、複雑な整数計画手順に依存しています。^{[ 6 ]}

より抽象的に言えば、これらの問題はどちらも、入力が部分順序集合と整数Wで構成される問題として定式化できます。望ましい出力は、部分順序集合の要素に整数レベルの数値を割り当てることです。つまり、x < y が部分順序の関連する要素の順序対である場合、xに割り当てられる数値はyに割り当てられる数値よりも小さく、最大でW個の要素に同じ数値が割り当てられ、割り当てられた数値の最小値と最大値の差が最小になるようにします。

コフマン・グラハムアルゴリズムは以下の手順を実行します。^{[ 4 ]}

1. 部分順序を推移的縮約または被覆関係によって表現します。これは、 x < yの場合にxからyへのエッジを持ち、 x < z < yとなるような部分順序の3 番目の要素z が存在しない有向非巡回グラフ G です。コフマン・グラハム アルゴリズムのグラフ描画アプリケーションでは、結果として得られる有向非巡回グラフは描画中のグラフと同じではない可能性があり、スケジューリング アプリケーションでは、入力のすべての先行制約に対してエッジを持たない可能性があります。どちらの場合も、推移的縮約は部分順序を定義するために不要な冗長なエッジを削除します。
2. Gの位相順序を構築します。この順序では、頂点は、その流入する隣接頂点の位置の集合によって辞書式順序で並べられます。そのためには、頂点を 1 つずつ順序に追加します。各ステップでは、追加する頂点vを選択します。このとき、 vの流入する隣接頂点はすべて既に部分順序の一部であり、かつ、vの最も最近追加された流入隣接頂点が、 vの代わりに追加できる他のどの頂点の最も最近追加された流入隣接頂点よりも前になるようにします。2 つの頂点の最も最近追加された流入隣接頂点が同じ場合、アルゴリズムは、2 番目に最近追加された流入隣接頂点が前である頂点を優先して、同順位を解消します。
3. Gの頂点を、前のステップで構築したトポロジカル順序の逆の順序でレベルに割り当てます。各頂点vについて、vの任意の出力隣接頂点の最上位レベルより少なくとも 1 ステップ高いレベル、既に W 個の要素が割り当てられていないレベル、および次の 2 つの制約を満たす可能な限り低いレベルに v を追加します。