Hatena::ブログ(Diary)

cocoatomo衝動日記

2011-01-17 大学数学の第一歩

[][][][][] グラフのはなし・その11 00:49  グラフのはなし・その11 - cocoatomo衝動日記 を含むブックマーク

さて前回 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]

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

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

あとがき

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

次回はこの色付けがどのように役立つのか, やや理論寄りな話をしたいと思います.

理論と言ってもできるだけ分かりやすく書くつもりなので, 紙とペン, 鉛筆を用意しておいてください.

それでは.

2011-01-16 大学数学の第一歩

[][][][][] グラフのはなし・その10 23:27  グラフのはなし・その10 - cocoatomo衝動日記 を含むブックマーク

さて今回は 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 で作っています.

完成をお楽しみに.