Pythonのgenerator(2) グラフ探索(1)のつづき。

こんな感じでノードクラスというものを作ってみます。フィールドは自分のノード名と隣接するノードインスタンスのリストとしました。

class Node:
    def __init__(self, name):
        self.name = name
        self.nodelist = []
    def add(self, list):
        self.nodelist += list

このクラスを使って先日のものと同じグラフを作ると

n1 = Node("a")
n2 = Node("b")
n3 = Node("c")
n4 = Node("d")
n5 = Node("e")
n6 = Node("f")

n1.add([n2, n6])
n2.add([n1, n3, n5])
n3.add([n2, n4, n5, n6])
n4.add([n3])
n5.add([n2, n3, n6])
n6.add([n1, n3, n5])

これに対する探索用ジェネレータはこんな感じ。再帰はなくしました。深さ優先はスタックを、幅優先はキューを使うと簡単。深さ優先のほうで隣接するノードのリストをひっくり返しているのは先日と同じ出力を得るためです。

def graph_depth2(node):
    route = []
    stack = []
    stack.append(node)
    while stack:
        n = stack.pop()
        if n not in route:
            for l in n.nodelist[::-1]:
                if l not in route:
                    stack.append(l)
            yield n.name
            route.append(n)

def graph_breadth2(node):
    route = []
    queue = []
    queue.append(node)
    while queue:
        n = queue.pop(0)
        for l in n.nodelist:
            if l not in route and l not in queue:
                queue.append(l)
        yield n.name
        route.append(n)

実際に探索させてみると

>>> for t in graph_depth2(n1):
    print t,

a b c d e f

>>> for t in graph_depth2(n3):
    print t,

c b a f e d

>>> for t in graph_breadth2(n1):
    print t,

a b f c e d

>>> for t in graph_breadth2(n3):
    print t,

c b d e f a

先日と同じ結果に。

もう一個のほうでも

n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n6 = Node(6)
n7 = Node(7)
n8 = Node(8)
n9 = Node(9)
n10 = Node(10)
n11 = Node(11)

n1.add([n2, n5])
n2.add([n1, n3, n5])
n3.add([n2, n4, n9])
n4.add([n3, n5])
n5.add([n1, n2, n4, n6, n7])
n6.add([n5, n9])
n7.add([n5, n8])
n8.add([n7])
n9.add([n3, n6, n10])
n10.add([n9, n11])
n11.add([n10])

>>> for t in graph_depth2(n1):
    print t,

1 2 3 4 5 6 9 10 11 7 8

>>> for t in graph_depth2(n9):
    print t,

9 3 2 1 5 4 6 7 8 10 11

>>> for t in graph_breadth2(n1):
    print t,

1 2 5 3 4 6 7 9 8 10 11


>>> for t in graph_breadth2(n9):
    print t,

9 3 6 10 2 4 5 11 1 7 8

当然同じ結果に。

先日は距離を導入してダイクストラでもやってみようと思ったんですが、ほとんど変わらなそうなので止めました。リストに追加する際に始点からの距離を計算して、ポップする時に一番始点から近いノードを拾って来ればいいだけですし。

ジェネレータのメリットというのは簡潔さとメモリ使用量の削減にあるので、再帰を使ったり、複雑な制御構造を持たせたりするのは避けた方がよいんでしょうね。