Implementazione di un grafo diretto in pitone

Question

Ho letto Python Patterns - Implementing Graphs. Tuttavia questa implementazione è inefficiente per ottenere i bordi che puntano a un nodo.

In altri linguaggi una soluzione comune utilizza un array bidimensionale, ma per farlo in Python sarebbe necessario un elenco di elenchi. Questo non sembra pietonico.

Che cosa è un'implementazione di un grafico diretto in python dove trovare tutti i nodi con i bordi da e verso un nodo (come due elenchi separati) è veloce?

Answer 1

SciPy offre routine Grafico efficienti se l'efficienza computazionale o calcolo scientifico è la vostra preoccupazione:

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

Answer 2

Date un'occhiata al Pygraph. L'ho usato un po 'per i grandi grafici diretti (e non orientati) senza problemi di memoria o di runtime, sebbene sia tutto implementato in Python, quindi un'implementazione avvolta in C++ potrebbe essere molto veloce.

Answer 3

questo non risponde alla tua domanda grafico, ma si può certamente implementare un elenco 2D in Python senza ricorrere a elenchi delle liste in almeno due modi:

si può semplicemente utilizzare un dizionario:

import collections 
t = collections.defaultdict(int) 

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

Questo ha anche il vantaggio che è scarso.

Per un approccio più elaborato, ma che richiede più lavoro, è possibile utilizzare un elenco 1d e calcolare l'indice utilizzando le coordinate 2D insieme all'altezza e alla larghezza della tabella.

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

Un'altra libreria che è possibile utilizzare è NetworkX. Fornisce un'implementazione di directed graphs che fornisce funzioni per ottenere i bordi in entrata DiGraph.in_edges() e i bordi in uscita DiGraph.out_edges() per insiemi arbitrari di nodi. I campioni di utilizzo sono forniti nella documentazione collegata, ma sfortunatamente non ho visto alcun dettaglio sull'efficienza o sul tempo di esecuzione.