グラフのはなし・その10

さて今回は C3 アルゴリズムトポロジカルソートで書けることを示してみましょう.

戦略

さて C3 アルゴリズムの肝は何だったかと言うと, それぞれの親クラスにとっての祖先クラスの順序と, 親クラスどうしの順序が食い違わないように, 祖先クラスを並べることでした. その操作を merge 関数で行っていたのですね.


トポロジカルソートでもこれを真似してみましょう.
注意する点としては, このブログで出したトポロジカルソートのアルゴリズムでは, リストに点を追加していって最後に引っ繰り返していることです.

なので, あるクラスの親クラスリストでは順序を逆に並べます.

実装して実行してみる

こんな例を使いましょう. この継承関係は食い違いは起こしていませんね? 確認してみてください.

クラス: 親クラス
B1: A
B2: A
C1: B1, B2
C2: B1, B2
D: C1, C2

このような継承関係を Python スクリプトで書くとこうなります.

# クラスの準備
D = PyClass('D')
C1 = PyClass('C1')
C2 = PyClass('C2')
B1 = PyClass('B1')
B2 = PyClass('B2')
A = PyClass('A')

# 矢印の準備
D.parents = [C2, C1]
C1.parents = [B2, B1]
C2.parents = [B2, B1]
B1.parents = [A]
B2.parents = [A]

優先度とは逆に親クラスが並べてあるのが分かりますね.

さて先祖クラスの順序を求める以下の Python スクリプトを動かしてみましょう.
コメントや文字列が少し変更されてますが, スクリプトの中身はほとんど昨日使っていたものと同じです.
(Python2.7 で動くことを確認しています. Python2.6 や Python3.1 でも動くはずです.)

# -*- coding: utf-8 -*-
class PyClass(object):
    def __init__(self, name=''):
        self.name = name
        self.checked = False
        self.parents = []

    def __str__(self):
        return self.name

    def __repr__(self):
        return str(self)

# クラスの準備
D = PyClass('D')
C1 = PyClass('C1')
C2 = PyClass('C2')
B1 = PyClass('B1')
B2 = PyClass('B2')
A = PyClass('A')

# 矢印の準備
D.parents = [C2, C1]
C1.parents = [B2, B1]
C2.parents = [B2, B1]
B1.parents = [A]
B2.parents = [A]

# 探索完了の記録用リスト
searched = []

# クラスの継承関係を探索する
def dfs(klass):
    print('-> {0.name}'.format(klass))
    if klass.checked:
        print(u'{0.name} はチェック済み'.format(klass))
        print('<- {0.name}'.format(klass))
        return

    klass.checked = True
    for parent in klass.parents:
        dfs(parent) # さらに継承関係を探索する
    else:
        print(u'{0.name} から引き返す'.format(klass)) # 祖先クラスの探索が終わった引き返す

    global searched
    searched.append(klass) # 探索が完了したら記録
    print('{1} を追加: {0}'.format(searched, klass))
    print('<- {0.name}'.format(klass))


if __name__ == '__main__':
    dfs(D)
    searched.reverse()
    print(searched)

さて, みなさんの環境で動かすことはできたでしょうか?
スクリプトの動きについてはコメントや出力メッセージでなんとなく分かるように作ってあります. (分かりづらければコメントくださいな.)

ちゃんと動けばこんな出力になっているはずです.

-> D
-> C2
-> B2
-> A
A から引き返す
A を追加: [A]
<- A
B2 から引き返す
B2 を追加: [A, B2]
<- B2
-> B1
-> A
A はチェック済み
<- A
B1 から引き返す
B1 を追加: [A, B2, B1]
<- B1
C2 から引き返す
C2 を追加: [A, B2, B1, C2]
<- C2
-> C1
-> B2
B2 はチェック済み
<- B2
-> B1
B1 はチェック済み
<- B1
C1 から引き返す
C1 を追加: [A, B2, B1, C2, C1]
<- C1
D から引き返す
D を追加: [A, B2, B1, C2, C1, D]
<- D
[D, C1, C2, B1, B2, A]

探索が完了すると無事に正しい先祖クラスの順序になっていますね.

問題点

さてこのスクリプトには 1 つ問題があります. それは何でしょうか?

そうです. 継承関係の食い違いがあっても実行できて, 何らかの結果が出てきてしまうことです.
これはどこに問題があったのでしょうか?


PyClass というクラスのオブジェクトには checked というフィールドがあり, ここの値に「あるクラスが既に探索されたか?」という情報 (真偽値) を保存しておき二重探索を防いでいました.

しかし実は, 継承関係の食い違いを見付け出すためには真と偽の 2 つの値では不足していて, 「未探索」「探索中」「探索済」の 3 種類の値が無いといけないのです.


深さ優先探索アルゴリズムから修正しないといけないので, また明日以降に今のスクリプトを改造していきましょう.

あとがき

なんだか最初の順序のはなしからだいぶ離れてしまったように感じますか?
これでも当初の目論見どおりなのです.

ここ最近, グラフやグラフアルゴリズムの勉強をしていたのですが, そこでふと「グラフアルゴリズムって, 点の整列を行っている」ことに気付いたのです.


「もしかして,『順序』という視点でグラフの話ができないか? それに最愛の言語 Pythonmro (method resolution order, メソッド解決順序) もグラフアルゴリズムだ. そして HadoopMapReduce のジョブフローもグラフと見れ, その上のアルゴリズムは重要になるだろう. よし単純な順序の話を切り口に, 主にグラフの話しをしよう.」


こう思ってこの連載はスタートしました.
1ヶ月ネタが続くか不安でしたが, なんとか折り返し地点まで来れました.
これも毎日読んでいてくださるみなさまのおかげです.

後半も気を引き締めて, 回を落とさないように頑張ります.
よろしくです.

追伸

グラフアルゴリズムを解説するときは, グラフィカルな表示も欲しいですよね.
自分も欲しいです.

そう思ったので現在鋭意製作中です.
今は PyOpenGL で作っています.

完成をお楽しみに.