在python中實現有向圖

我讀Python Patterns - Implementing Graphs。然而，這種實現方式對於獲取指向節點的邊來說效率不高。在python中實現有向圖

在其他語言中，一個常見的解決方案是使用二維數組，但在Python中這樣做需要一個列表清單。這似乎並不pythonic。

python中的有向圖的實現是什麼？在哪裏找到所有節點的邊和節點（作爲兩個單獨的列表）是快速的？

2012-08-08 jan

爲什麼列表不是Pythonic？ 2D列表在Python中非常常用。您還可以使用完善的[numpy.ndarray]（http://docs.scipy.org/doc/numpy/reference/arrays.ndarray.html），它實現n維數組並支持按行或按柱。 – 2012-08-08 17:09:54

SciPy的能夠提供高效的圖形程序，如果計算效率和科學計算是您的關心：

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

來源

2012-08-08 17:10:41 Edmon

我相信，壓縮稀疏矩陣甚至比正常的二維數組更好。空間效率更高。 – JAB 2012-08-08 18:05:54

看一看的Pygraph。對於沒有內存或運行時問題的大型定向（和不定向）圖形，我已經使用了它很多，儘管它全部在Python中實現，所以C++包裝的實現可能非常快。

來源

2012-08-08 17:32:42 Pyrce

這不回答你的問題圖形，但你肯定可以實現在Python 2D名單沒有至少兩種方式訴諸列表的列表：

您只需使用一本字典：

import collections 
t = collections.defaultdict(int) 

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

這也有其優點，它是稀疏的。

對於更好的方法，但需要更多工作的方法，可以使用1d列表並使用2D座標以及表格的高度和寬度計算索引。

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]

來源

2012-08-08 18:07:51 Nathan

另一個可以使用的庫是NetworkX。它提供了一個實現directed graphs，它提供函數來獲得任意節點集合的邊DiGraph.in_edges()和出邊DiGraph.out_edges()。使用示例在鏈接的文檔中提供，但不幸的是我沒有看到有關效率或運行時間的任何細節。

來源

2012-08-08 18:31:23

在python中實現有向圖

回答

相關問題