Pythonで有向グラフを実装する

Question

私はPython Patterns - Implementing Graphsを読んでいます。しかしながら、この実装は、ノードを指すエッジを得るためには非効率的である。

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

ノードとの間でエッジを持つノードを（2つの別々のリストとして）見つけるのが高速な、Pythonの有向グラフの実装は何ですか？

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

Answer 1

scipyのダウンロードは、効率的なグラフのルーチンを提供しています。私はPythonで実装されていますが、メモリや実行時の問題のない大きな方向付け（無向グラフ）グラフに対してはかなり使用しました。そのため、C++のラップされた実装ははるかに高速になる可能性があります。

Answer 2

はPygraphを見てみましょう：計算効率や科学的なコンピューティングは、あなたの関心事である場合

Answer 3

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

あなたは単に辞書を使用することができます。

import collections 
t = collections.defaultdict(int) 

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

これはまた、それが疎であるという利点を有する。

より多くの作業が必要な場合は、1dリストを使用して、テーブルの高さと幅とともに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

使用できる別のライブラリはNetworkXです。 directed graphsのインプリメンテーションでは、任意のノードセットに対してincomming edge DiGraph.in_edges()およびoutgoing edges DiGraph.out_edges()を取得する機能を提供します。 リンクされたドキュメントに使用サンプルが提供されていますが、残念ながら効率や実行時間についての詳細は表示されませんでした。