プログラミング言語論の最近のブログ記事

ここで、矢印の向きと大小関係が一致するということから、双方向の矢印は存在してはいけない。

また、グラフに閉路（循環）が存在してもいけない。それは下のグラフを見れば分かると思うが、このグラフにトポロジカルソートを行うのは不可能だ。
下の状態では、３→１のところで、条件を満たしていない

で、これをどういうアルゴリズムで出来てるのかというと・・・


あー、もうメンドクサイからレポートのコピペ

下のようなメソッドを書いて、for文でこのメソッドの引数を変えながら順番に呼び出していけばよい


    /**      * トポロジカルソートを行い、閉路があるかを戻り値に示す。      *      * @param final int i 現在いるノード      * @param final int n ノードの数      * @return boolean グラフに閉路がなければtrue, あればfalse      */     private boolean visit(final int i, final int n) {         int j,v;         if (n < 0 || n >= NMAX) return false;         if (i < 0 || i >= n) return false;         visited[i] = JUST;                  for(j=0; j<n; j++) {             //ノードiからノードjへのアーク（矢印）がない場合、次を訪問             if((adjacent[j][i] == UNCONNECTED)) continue;             //ノードjに訪れたことある場合             if((v=visited[j]) != NEVER) {                 //ノードjが一周してノードiに戻ってきたとき、閉路を検出したとしてfalseを返す                 if (v == JUST) return false;             //ノードjに訪れたことがない場合、ノードjを始点としてその次を訪問し、             //その先以降に閉路があればfalseを返す。             } else if (!visit(j, n)) return false;         }         visited[i] = ONCE;         result[k] = i;         k++;         return true;     }




最後に、せっかくレポートで書いたので外部仕様を

【visitメソッドの外部仕様】
閉路検出機能付きのトポロジカルソートを行う。
トポロジカルソートとは、ある有向グラフが与えられた時に、矢印（アーク）の向きと大小関係が一致するように、それぞれ異なった整数をノードに割り当てることである。

○入力
・iは現在いるノードの位置
・nはノードの数

○出力
・jは、ノードを順番に調べる際のカウンタ
・vは、ノードiからアークのあるノードを保持する一時変数
・adjacentは、あるノードから別のノードへのアーク（矢印）が存在するかを示す2次元配列。アークは一方方向のみであるので、adjacent[i][j]==CONNECTEDである場合、adjacent[j][i]は常にUNCONNECTEDでなければならない。また、adjacent[i][i]は常にUNCONNECTEDである。
・visited、そのノードは訪問済みか、訪問中か、まだ訪問していないかを示す配列
・resultは、そのノードにおいて、トポロジカルソートの結果割り当てられた、トポロジカルソート値を示す保持する配列。また、resultの各要素はゼロから始まる自然数のいずれかで、数値が飛ぶことも重複することもない。
・    戻り値は、与えられた有向グラフから閉路が検出できればfalse、そうでなければtrue