グラフのはなし・その11

math ComputerScience order graph Python

さて前回 mro のトポロジカルソートを使った実装までできたのですが, mro の失敗が検知できない不十分なアルゴリズムで実装してしまいました.

今回はその不十分なところを修正するために, 今まで 2 つ (「未探索」と「探索済」) しかなかったノードの状態を 3 つ (「未探索」と「探索中」と「探索済」) に増やします.

ソースコード

改良したソースコードはこんなふうになります.

変わっている部分は PyClass オブジェクトの checked フィールドが color フィールドに変わり, その取る値が「真偽値」から 'WHITE', 'GRAY', 'BLACK' の 3 色になったところです.

それに合わせて, 探索の状態に応じて色を変えるようにし, 探索済をチェックするコードも色で判定するように変えました.
まずは実行してみてください.

# -*- coding: utf-8 -*-
class PyClass(object):
    def __init__(self, name=''):
        self.name = name
        self.color = 'WHITE'  # 最初はみんな白
        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.color == 'BLACK' or klass.color == 'GRAY': # 色のチェック
        print(u'{0.name} はチェック済み. 色: {0.color}'.format(klass))
        print('<- {0.name}'.format(klass))
        return

    klass.color = 'GRAY' # 探索中の色に塗る
    for parent in klass.parents:
        dfs(parent) # さらに継承関係を探索する

    print(u'{0.name} を黒に塗って引き返す'.format(klass)) # 祖先クラスの探索が終わった引き返す
    klass.color = 'BLACK' # 探索完了の色に塗る
    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 はチェック済み. 色: BLACK
<- A
B1 を黒に塗って引き返す
B1 を追加: [A, B2, B1]
<- B1
C2 を黒に塗って引き返す
C2 を追加: [A, B2, B1, C2]
<- C2
-> C1
-> B2
B2 はチェック済み. 色: BLACK
<- B2
-> B1
B1 はチェック済み. 色: BLACK
<- B1
C1 を黒に塗って引き返す
C1 を追加: [A, B2, B1, C2, C1]
<- C1
D を黒に塗って引き返す
D を追加: [A, B2, B1, C2, C1, D]
<- D
[D, C1, C2, B1, B2, A]

引き返すときに色を黒く塗っているのが分かりますね.

またごちゃごちゃするので出力はしていませんが, あるクラスの探索を始めるときにはそのクラスを灰色に塗っています.

あとがき

今日のところはここまでにします.

次回はこの色付けがどのように役立つのか, やや理論寄りな話をしたいと思います.
理論と言ってもできるだけ分かりやすく書くつもりなので, 紙とペン, 鉛筆を用意しておいてください.

それでは.