Python でグラフ分析番外編・Pure Pythonのみで簡易グラフ分析

このところネットワーク分析 (Rで学ぶデータサイエンス 8)に沿ってグラフ分析をやってて、それにハマってるわけだが、いろいろやっているうちに Python の生みの親のグイド・ヴァンロッサム先生自らによる、Python Patterns - Implementing Graphs（英語）という、Pure Python でグラフを実装する方法について説明した記事に遭遇した。

こんなにシンプルなコードでグラフが表現できるのか、と改めて Python の使いやすさに感心しつつ、オリジナルの記事の内容を Python3 で実装したところ、幾つかバージョンの違いによる変更点があったのでメモっておく。

Pure Python によるグラフ実装の要点

グイド先生の記事では list と dictionary を組み合わせたデータ構造でグラフを表現できる、としている。思うに、このデータ構造と Python の強力な list や dictionary を操作するメソッドがグラフ実装のキモだと思う。

list と dictionary でエッジリスト（のようなもの）を表現する

dictionary と list を組み合わせた次のようなデータ構造によりグラフ（ちなみに、有向グラフ）を表現できる。

graph = {'A': ['B', 'C'],  
             'B': ['C', 'D'],  
             'C': ['D'],  
             'D': ['C'],  
             'E': ['F'],  
             'F': ['C']}

ここで、dictionary のキーがノードの起点、そのキーの値が、起点から遷移できる遷移先のノードである。

特定のノードからノードへのパスを見つける

特定のノードからノードへのパスを見つけるのに、Python の強力な機能の一つ、関数の再帰呼び出しを使って次のように実装している。

def find_path(graph, start, end, path=[]):  
        path = path + [start]  
        if start == end:  
            return path  
        if not graph.has_key(start):  
            return None  
        for node in graph[start]:  
            if node not in path:  
                newpath = find_path(graph, node, end, path)  
                if newpath: return newpath  
        return None  
  
## 実行結果はこんな感じ  
>>> find_path(graph, 'A', 'D')  
['A', 'B', 'C', 'D']  
>>>

ちなみに、すべてのルートを見つけるのはこんな感じ。

def find_all_paths(graph, start, end, path=[]):  
        path = path + [start]  
        if start == end:  
            return [path]  
        if not graph.has_key(start):  
            return []  
        paths = []  
        for node in graph[start]:  
            if node not in path:  
                newpaths = find_all_paths(graph, node, end, path)  
                for newpath in newpaths:  
                    paths.append(newpath)  
        return paths  
  
## 実行結果  
>>> find_all_path(graph, 'A', 'D')  
[['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]  
>>>

やはり再帰呼び出しを使って、次のルートを探す処理を実装している。

グラフのノード間の最短距離を求める

def find_shortest_path(graph, start, end, path=[]):  
        path = path + [start]  
        if start == end:  
            return path  
        if not graph.has_key(start):  
            return None  
        shortest = None  
        for node in graph[start]:  
            if node not in path:  
                newpath = find_shortest_path(graph, node, end, path)  
                if newpath:  
                    if not shortest or len(newpath) < len(shortest):  
                        shortest = newpath  
        return shortest  
  
## 実行結果  
>>> find_shortest_path(graph, 'A', 'D')  
['A', 'C', 'D']  
>>>

こんな簡単にグラフが実装できるなんて Python ってスゴイ。

参考：
Python Patterns - Implementing Graphs（英語）