Implementando un gráfico dirigido en python

Question

Leo Python Patterns - Implementing Graphs. Sin embargo, esta implementación es ineficiente para obtener los bordes que apuntan a un nodo.

En otros lenguajes, una solución común es utilizar una matriz bidimensional, pero para hacerlo en Python sería necesaria una lista de listas. Esto no parece pitónico.

¿Qué es una implementación de un grafo dirigido en python donde encontrar todos los nodos con bordes hacia y desde un nodo (como dos listas separadas) es rápido?

Answer 1

Scipy ofrece rutinas de gráficos eficientes si la eficiencia computacional o la computación científica es su preocupación:

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

Answer 2

Tome un vistazo a la Pygraph. Lo he usado bastante para gráficos grandes dirigidos (y no dirigidos) sin problemas de memoria o tiempo de ejecución, aunque todo está implementado en Python, por lo que una implementación envuelta en C++ podría ser mucho más rápida.

Answer 3

esto no responde a su pregunta gráfica, pero que sin duda puede aplicar una lista en Python 2D sin tener que recurrir a las listas de listas en por lo menos dos maneras:

puede simplemente usar un diccionario:

import collections 
t = collections.defaultdict(int) 

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

Esto también tiene la ventaja de que es escaso.

Para un enfoque más elegante, pero que requiere más trabajo, puede usar una lista 1d y calcular el índice utilizando las coordenadas 2D junto con el alto y el ancho de la tabla.

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

Otra biblioteca que podría utilizar es NetworkX. Proporciona una implementación de directed graphs que proporciona funciones para obtener bordes entrantes DiGraph.in_edges() y bordes salientes DiGraph.out_edges() para conjuntos arbitrarios de nodos. Las muestras de uso se proporcionan en la documentación vinculada, pero desafortunadamente no vi ningún detalle sobre la eficiencia o el tiempo de ejecución.