Implementacja skierowanego wykresu w pythonie

Question

Przeczytałem Python Patterns - Implementing Graphs. Jednak ta implementacja jest nieefektywna w uzyskiwaniu krawędzi wskazujących na węzeł.

W innych językach powszechnym rozwiązaniem jest użycie dwuwymiarowej tablicy, ale w tym celu w Pythonie będzie wymagana lista list. To nie wygląda na pyton.

Co to jest implementacja skierowanego wykresu w pythonie, gdzie znalezienie wszystkich węzłów z krawędziami do iz węzła (jak dwie oddzielne listy) jest szybkie?

Answer 1

scipy oferuje efektywne procedury Graph jeśli wydajność obliczeniowa lub obliczenia naukowe jest twoim problemem:

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

Answer 2

Spójrz na Pygraph. Używałem go całkiem sporo w przypadku dużych grafów skierowanych (i nieokierunkowanych) bez problemów związanych z pamięcią lub czasem wykonania, chociaż wszystko to zostało zaimplementowane w Pythonie, więc implementacja zapakowana w C++ może być bardzo szybka.

Answer 3

To nie jest odpowiedź na wykresie pytanie, ale z pewnością można wdrożyć 2D listę w Pythonie, bez uciekania się do list list w co najmniej dwa sposoby:

można po prostu użyć słownika:

import collections 
t = collections.defaultdict(int) 

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

Ma to tę zaletę, że jest rzadkie.

Dla bardziej wyrafinowanego podejścia, ale wymagającego więcej pracy, można użyć listy 1d i obliczyć indeks przy użyciu współrzędnych 2D wraz z wysokością i szerokością stołu.

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

Kolejną biblioteką, której można użyć jest NetworkX. Zapewnia implementację directed graphs, która zapewnia funkcje uzyskiwania kolejnych krawędzi DiGraph.in_edges() i wychodzących krawędzi DiGraph.out_edges() dla dowolnych zestawów węzłów. Przykłady użycia są dostępne w połączonej dokumentacji, ale niestety nie widziałem żadnych szczegółów dotyczących wydajności ani czasu działania.