トポロジカルソート

トポロジカルソート

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

有向非巡回グラフとは

Directed Acyclic Graph で DAG ともいう。

  • 有向グラフ
    • リンクが一方通行。頂点A→Bにリンクがあっても、B→A方向には通れない
  • 非巡回グラフ
    • 閉路が無い。ある頂点Aから出発して、Aに戻ってくるような経路が無い
1.A→B  2.A→B
  ↑  ↓    ↓  ↓
  D←C    D→C
   閉路     閉路じゃない

トポロジカルソートとは

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

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

上記2.のトポロジカルソート例
    ┌───v
A→B  D→C
└───^

DAGでない1.は、どこかに左向きのリンクができてしまう
A→B→C→D
 ^----------┘

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

アルゴリズム

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

  • nに流入するリンク数
  • nから流出するリンクの流出先ノードのリスト
B      E  この場合、
  ↘  ↗    Aに流入するリンク数はBCDの「3」
C→A→F  Aからの流出先ノードは「E,F,G」となる
  ↗  ↘
D      G  

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

  • 流入リンク数が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を除いた集合」という意味。

A→B→C→E
  \      ↗
    →Dー→F

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

  • ABDFCE
  • ADBFCE
  • ADFBCE
  • ABCDFE
  • ABDCFE
  • ADBCFE
  • ABCDEF
  • ABDCEF
  • ADBCEF

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

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

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

つまり、$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フラグ)

今回の例では、たとえばDからはE,Fへ流出するので、Dの値は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])

programming_algorithm/graph_theory/topological_sort.txt · 最終更新: 2017/10/08 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0