トポロジカルソート

有向非巡回グラフを順に並べるソートアルゴリズム。

有向非巡回グラフとは

Directed Acyclic Graph で DAG ともいう。

有向グラフ
- リンクが一方通行。頂点Ａ→Ｂにリンクがあっても、Ｂ→Ａ方向には通れない
非巡回グラフ
- 閉路が無い。ある頂点Ａから出発して、Ａに戻ってくるような経路が無い

1.Ａ→Ｂ  2.Ａ→Ｂ
  ↑  ↓    ↓  ↓
  Ｄ←Ｃ    Ｄ→Ｃ
   閉路     閉路じゃない

トポロジカルソートとは

DAGでは、どのリンクに対しても、流入元ノードが前、流出先ノードが後に来るように1列に並び替えることができる。これをトポロジカルソートという。

「リンクが常に右向きになっている」と言い換えてもよい。

上記2.のトポロジカルソート例
    ┌───v
Ａ→Ｂ  Ｄ→Ｃ
└───^

DAGでない1.は、どこかに左向きのリンクができてしまう
Ａ→Ｂ→Ｃ→Ｄ
 ^----------┘

ソート結果は一意に決まるとは限らない。2.の場合、ＡＤＢＣもソート結果の1つである。

アルゴリズム

各ノードnにつき、以下の情報を保持する

nに流入するリンク数
nから流出するリンクの流出先ノードのリスト

Ｂ      Ｅ  この場合、
  ↘  ↗    Ａに流入するリンク数はＢＣＤの「3」
Ｃ→Ａ→Ｆ  Ａからの流出先ノードは「Ｅ,Ｆ,Ｇ」となる
  ↗  ↘
Ｄ      Ｇ

また、以下のデータを作成する

流入リンク数が0であるノードのセットS
- DAGなら最低1つは存在する
暫定ソート結果を保持する空リストL

以下の擬似コードでソートできる

while Sが空になるまで
    Sから任意のノードnをpop
    Lの末尾にnを追加
    foreach m in nから流出する先のノードリスト
        mの流入リンク数を1減らす
        if mの流入リンク数 == 0
            mをSに追加

if Lの長さ == ノード数N
    Lがソート結果
else
    グラフはDAGでなく、トポロジカルソート不可能

# ・ノードIDは、0～N-1とする
# ・以下のデータは既に作られているとする
#   inc[n] = nに流入するリンク数(int)
#   out[n] = nからの流出先のノード集合(list or set)

S = {i for i, c in enumerate(inc) if c == 0}
L = []

while S:
    n = S.pop()
    L.append(n)
    for m in out[n]:
        inc[m] -= 1
        if inc[m] == 0:
            S.add(m)

# DAGであることは前提として、チェックは省略
print(L)

Sに同時に複数のノードが入っている瞬間があると、pop時にどれが選ばれるかによってソート結果が変わる。

ここで、例えばSに優先度キューを用いるとノードIDが小さい順に取り出され、小さいノードを優先して前に持ってくるよう固定される。

数え上げ

ソート結果の1つを求めるなら上記でよいが、「ソート結果としてあり得る並び方が何通りになるか」という問題は、現実的な時間では解けない。

オーダーは、動的計画法を上手く使うことでO(N * 2^N)となるので、N=20くらいまでなら何とかなる。

全ノードの集合をUとし、その部分集合Sを考える。

$f(S) = Sのみを使ったソート結果の候補数$ とする。f(U)を求めればよい。

この時、以下の関係が成り立つ。

Sの中で、「ソート結果で最も右に置くことができるノード」（Sの中に流出先ノードがない、末端ノード）の集合をTとすると、

$f(S) = \displaystyle \sum_{n \in T} f(S \setminus \{n\})$

となる。$S \setminus \{n\}$は、「Sからnを除いた集合」という意味。

例

Ａ→Ｂ→Ｃ→Ｅ
  ＼      ↗
    →Ｄー→Ｆ

このようなグラフの場合、ソート結果は以下の9通りあるが、

ABDFCE
ADBFCE
ADFBCE
ABCDFE
ABDCFE
ADBCFE
ABCDEF
ABDCEF
ADBCEF

最も右に置くことができるのは、ＥかＦである。

つまり、$f(\{ABCDEF\}) = f(\{ABCDE\}) + f(\{ABCDF\})$ ということになる。

Eを除いたABCDFに付いて考えると、最も右に置くことができるのはＣかＦである。

つまり、$f(\{ABCDF\}) = f(\{ABCD\}) + f(\{ABDF\})$

同様に、$f(\{ABCD\}) = f(\{ABC\}) + f(\{ABD\})$……と求めていき、$f(\phi)=1$で確定する。

集合がキーになる動的計画法で、要素数が高々32個くらいまでなら、集合をbitフラグで管理するとよい。bitDPという。

{ABCDEF} = 0x111111、{A,C,F} = 0x100101 という感じだ。これならメモリも少なく済むし、要素が含まれるかのチェックもbit演算で済むため速い。

わかりやすくするため要素数の多い方から考えていったが、実際には要素数が少ない方から計算していく。

「候補数が確定した集合i」に、「新たに末尾に加えられるノードj」があれば、「iにjを加えた集合」の候補数に集合iの候補数を加算する。

iをforループで小さい方から回していくと、iに到達した時にはiに含まれる全ての要素kについて考慮が済んでおり、候補数が確定していることが保証される。

数え上げのアルゴリズム

各ノードnにつき、以下の情報を持っておく。

nからの流出先ノードの集合（bitフラグ）

今回の例では、たとえばＤからはＥ,Ｆへ流出するので、Ｄの値は0x110000 となる。

後は下記の擬似コードで求められる。iは候補数確定済みの部分集合、jはiの末尾に付け加えることが可能かチェック中のノードIDである。ノードIDは、0～N-1が振られているとする。

dp = サイズ2^Nの配列
dp[0] = 1

for i in 0～2^N-1
    for j in 0～N-1
        if 「集合iの中にjはまだ存在しない」 and 「jの流出先ノードにiの要素が含まれない」
            dp[iにjを加えた集合] += dp[i]

dp[2^N-1]が候補数

# b[n] = ノードnからの流出先ノードの集合のbitフラグ

dp = [0] * (1 << N)
dp[0] = 1
# ノードIDと対応するビット位置は繰り返し求めるので事前計算しておく
jbs = [(j, 1 << j) for j in range(N)]

for i in range(1 << N):
    for j, jb in jbs:
        if (i & jb) == 0 and (i & b[j]) == 0:
            dp[i | jb] += dp[i]

print(dp[-1])

目次