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

完成をお楽しみに.

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

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

今日は PerlPython のクラスの多重継承で使われているアルゴリズム C3 を紹介します.

多重継承メソッドを呼び出した場合, 複数の親クラスを持つので今呼び出しているメソッドがどの親に属しているのかを調べなければなりません.

そしてその順序も決めておき, 必ず決まったメソッドが呼ばれるようにしなくてはなりません.


それを実現する C3 アルゴリズムとはどんなものなのでしょうか?

C3 アルゴリズム概要

このページを参考にして解説を行います.

http://www.python.org/download/releases/2.3/mro/


数式で書いてしまえば,

¥mathrm{mro}(C) = ¥[C¥] + ¥mathrm{merge}(¥mathrm{mro}(P_1),¥quad ¥mathrm{mro}(P_2),¥quad ¥dots,¥quad ¥mathrm{mro}(P_n),¥quad ¥[P_1,¥quad P_2,¥dots,¥quad P_n¥])

([P1, P2,..., Pn] は C の親クラス)

となります.

[C] は C 1 つからなるリストで, その後ろの "+" はリストの結合です.

右辺で再度 mro 関数が呼び出されていますが, 親クラスを持たないクラス C に対して ¥mathrm{mro}(C) = Cと定義されるので, この計算はどこかで止まります.

merge 関数では引数に入ってきたリストの順序を崩さずに, 新たなリストを作っているので, まさにトポロジカルソートが行われています.

C3 アルゴリズムの動き

具体的な merge 関数の動きを見ていきましょう.

  1. まず, 先頭の引数 ¥mathrm{mro}(P_1) (実体はリスト) から先頭の元 P を取ってきます.
  2. P が他の引数 ¥mathrm{mro}(P_2),¥quad¥mathrm{mro}(P_3),¥dots,¥quad¥mathrm{mro}(P_n),¥quad¥[P_1,¥quad P_2,¥dots,¥quad P_n¥] のそれぞれの先頭にあるか, それとも含まれないか, をチェックします.
  3. そのチェックが通った場合は P を括り出します. (例はまた後で)
  4. もしそのチェックに通らなければ, ¥mathrm{mro}(P_2) に対して同じチェックを行います.
  5. 全ての引数でチェックが通らなければ ¥mathrm{mro} 失敗です.

言葉だけの説明では分かりづらいので, 具体例を扱っていきましょう. (何度も言ってますが, 具体例を考えるのはすごく重要です.)

クラス: 親クラス
C: B

単純な継承です. すごく簡単だし, わざわざ計算しなくてもすぐに分かりますが, 練習として解いてみましょう.

¥begin{align*}¥mathrm{mro}(C) &= ¥[C¥] + ¥mathrm{merge}(¥mathrm{mro}(B),¥quad ¥[B¥]) ¥¥ &= ¥[C¥] + ¥mathrm{merge}(¥[B¥],¥quad ¥[B¥]) ¥¥ &= ¥[C¥] + ¥[B¥] ¥¥ &= ¥[C,¥quad B¥]¥end{align*}

確かに望んだ結果が出てきましたね.


では次はもう少し出てくるクラスを増やしましょう.

クラス: 親クラス
C: B1, B2

単純な多重継承です.

¥begin{align*}¥mathrm{mro}(C) &= ¥[C¥] + ¥mathrm{merge}(¥mathrm{mro}(B_1),¥quad ¥mathrm{mro}(B_2) ¥[B_1,¥quad B_2¥]) ¥¥ &= ¥[C¥] + ¥mathrm{merge}(¥[B_1¥],¥quad ¥[B_2¥],¥quad ¥[B_1,¥quad B_2¥]) ¥¥ &= ¥[C¥] + ¥[B_1¥] + ¥mathrm{merge}(¥[¥],¥quad ¥[B_2¥],¥quad ¥[B_2¥]) ¥¥ &= ¥[C¥] + ¥[B_1¥] + ¥[B_2¥] ¥¥ &= ¥[C¥] + ¥[B_1,¥quad B_2¥] ¥¥ &= ¥[C,¥quad B_1,¥quad B_2¥]¥end{align*}


こんな継承関係を考えてみましょう. これは有名なダイヤモンド継承ですね.

クラス: 親クラス
C: B1, B2
B1: A
B2: A

¥begin{align*}¥mathrm{mro}(C) &= ¥[C¥] + ¥mathrm{merge}(¥mathrm{mro}(B_1),¥quad¥mathrm{mro}(B_2),¥quad¥[B_1,¥quad B_2¥]) ¥¥ &= ¥[C¥] + ¥mathrm{merge}(¥[B_1,¥quad A¥],¥quad ¥[B_2,¥quad A¥] ,¥quad¥[B_1,¥quad B_2¥])¥¥ &= ¥[C¥] + ¥[B_1¥] + ¥mathrm{merge}(¥[A¥],¥quad ¥[B_2,¥quad A¥],¥quad ¥[B_2¥] ) ¥¥ &= ¥[C¥] + ¥[B_1¥] + ¥[B_2¥] + ¥mathrm{merge}(¥[A¥],¥quad ¥[A¥],¥quad ¥[¥]) ¥¥ &= ¥[C¥] + ¥[B_1¥] + ¥[B_2¥] + ¥[A¥] ¥¥ &= ¥[C,¥quad B_1,¥quad B_2,¥quad A¥] ¥end{align}

今度はこんな計算になり, 上手く多重継承の先祖クラスの順序を扱えていますね.

4 段目で A ではなく B_2 が括り出されているのは, ¥mathrm{merge} 関数の第 2 引数¥[B_2,¥quad A¥] というリストがあり, この順序を守るためです.


では最後に mro に失敗する例を考えてみましょう.

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

この継承関係では C_1 の親クラスの順序と C_2 の親クラスの順序が食い違っているので, きちんと先祖クラスの順序が付けられません.

実際に Python でクラス D を作ろうとすると, 以下のようにエラーが出て作ることができません.

>>> A = object
>>> class B1(A): pass
... 
>>> class B2(A): pass
... 
>>> class C1(B1, B2): pass
... 
>>> class C2(B2, B1): pass
... 
>>> class D(C1, C2): pass
... 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: Error when calling the metaclass bases
    Cannot create a consistent method resolution
order (MRO) for bases B2, B1

さて ¥mathrm{mro} で計算してみましょう.

¥begin{align*}¥mathrm{mro}(D) &= ¥[D¥] + ¥mathrm{merge}(¥mathrm{mro}(C_1),¥quad ¥mathrm{mro}(C_2),¥quad ¥[C_1,¥quad C_2¥]) ¥¥ &= ¥[D¥] + ¥mathrm{merge}(¥[C_1,¥quad B_1,¥quad B_2,¥quad A¥],¥quad ¥[C_2,¥quad B_2,¥quad B_1,¥quad A¥],¥quad ¥[C_1,¥quad C_2¥]) ¥¥ &= ¥[D¥] + ¥[C_1,¥quad C_2¥] + ¥mathrm{merge}(¥[B_1,¥quad B_2,¥quad A¥],¥quad ¥[B_2,¥quad B_1,¥quad A¥],¥quad ¥[¥])¥end{align*}

とここまできて困ってしまいました. B1 と B2 の順序をどちらを先としてもうまく ¥mathrm{merge} できません.

なので ¥mathrm{mro} の計算は失敗し, ここで終了です.

あとがき

今日はトポロジカルソートが使われている一例として, Pythonmro を扱いました.

昨日のトポロジカルソートとのつながりが話せていないので, 次回は Pythonmro を実装し, 今までのトポロジカルソートと比べてみます.