python - Python での有向グラフの実装

Question

Python Patterns - Implementing Graphsを読みました。ただし、この実装は、ノードを指すエッジを取得するには非効率的です。

他の言語では一般的な解決策は 2 次元配列を使用することですが、Python でこれを行うにはリストのリストが必要になります。これはpythonicではないようです。

ノードへのエッジとノードからのエッジを持つすべてのノードを (2 つの個別のリストとして) 高速に見つける Python の有向グラフの実装は何ですか?

Answer 1

使用できる別のライブラリはNetworkXです。任意のノード セットの入力エッジと出力エッジを取得する関数を提供する有向グラフの実装を提供します。リンクされたドキュメントで使用例が提供されていますが、残念ながら、効率や実行時間に関する詳細はわかりませんでした。DiGraph.in_edges()DiGraph.out_edges()

Answer 2

計算効率または科学計算が懸念される場合、Scipyは効率的なグラフルーチンを提供します。

http://docs.scipy.org/doc/scipy/reference/sparse.csgraph.html

Answer 3

これはグラフの質問には答えませんが、少なくとも 2 つの方法でリストのリストに頼ることなく、確かに Python で 2D リストを実装できます。

単純に辞書を使用できます。

import collections
t = collections.defaultdict(int)

t[0, 5] = 9
print t[0, 5]

これには、まばらであるという利点もあります。

より洗練されたアプローチではあるが、より多くの作業が必要な場合は、1 次元リストを使用し、2 次元座標とテーブルの高さと幅を使用してインデックスを計算できます。

class Table(object):
    def __init__(self, width, height):
        self._table = [None,] * (width * height)
        self._width = width

    def __getitem__(self, coordinate):
        if coordinate[0] >= width or coordinate[1] >= height:
            raise IndexError('Index exceeded table dimensions')
        if coordinate[0] < 0 or coordinate[1] < 0:
            raise IndexError('Index must be non-negative')
        return self._table[coordinate[1] * width + coordinate[0]]

    def __setitem__(self, coordinate, value):
        if coordinate[0] >= width or coordinate[1] >= height:
            raise IndexError('Index exceeded table dimensions')
        if coordinate[0] < 0 or coordinate[1] < 0:
            raise IndexError('Index must be non-negative')
        self._table[coordinate[1] * width + coordinate[0]] = value


t = Table(10,10)
t[0, 5] = 9
print t[0, 5]

Answer 4

Pygraphを見てください。メモリや実行時の問題のない大きな有向 (および無向) グラフにかなり使用しましたが、すべて Python で実装されているため、C++ でラップされた実装ははるかに高速です。