¿Cuál es la estructura de datos de gráficos más eficiente en Python?

votos
63

Necesito poder manipular un gráfico grande (10 ^ 7 nodos) en python. Los datos correspondientes a cada nodo / borde son mínimos, por ejemplo, un pequeño número de cadenas. ¿Cuál es la manera más eficiente, en términos de memoria y velocidad , de hacer esto?

Un dict de dicts es más flexible y más simple de implementar, pero intuitivamente espero que una lista de listas sea más rápida. La opción de lista también requeriría que mantenga los datos separados de la estructura, mientras que los dictados permitirían algo así:

graph[I][J][Property]=value

¿Qué sugieres?


Sí, debería haber sido un poco más claro sobre lo que quiero decir con eficiencia. En este caso particular lo digo en términos de recuperación de acceso aleatorio.

Cargar los datos en la memoria no es un gran problema. Eso se hace de una vez por todas. La parte que consume mucho tiempo visita los nodos para que pueda extraer la información y medir las métricas que me interesan.

No había considerado convertir cada nodo en una clase (las propiedades son las mismas para todos los nodos) pero parece que eso agregaría una capa adicional de sobrecarga. Esperaba que alguien tuviera alguna experiencia directa con un caso similar que pudieran compartir. Después de todo, los gráficos son una de las abstracciones más comunes en CS.

Publicado el 04/08/2008 a las 13:00
fuente por usuario
En otros idiomas...                            


7 respuestas

votos
51

Yo recomendaría encarecidamente que mires a NetworkX . Es un caballo de batalla probado en la batalla y la primera herramienta a la que recurren la mayoría de los tipos de "investigación" cuando necesitan analizar los datos basados ​​en la red. He manipulado gráficos con cientos de miles de bordes sin problemas en una computadora portátil. Su característica rica y muy fácil de usar. Se encontrará enfocándose más en el problema en cuestión que en los detalles en la implementación subyacente.

Ejemplo de generación y análisis de gráficos aleatorios Erdős-Rényi


"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

Las visualizaciones también son sencillas:

enter image description here

Más visualización: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Respondida el 26/08/2008 a las 18:43
fuente por usuario

votos
12

A pesar de que esta pregunta es ahora bastante viejo, creo que vale la pena mencionar mi propio módulo de Python para la manipulación gráfica llamada gráfico-herramienta . Es muy eficiente, ya que las estructuras de datos y algoritmos están implementados en C ++, con metaprograming plantilla, utilizando el Boost Graph Library. Por lo tanto su rendimiento (tanto en uso de memoria y tiempo de ejecución) es comparable a una biblioteca de C ++ puro, y puede ser órdenes de magnitud mejor que el código Python típico, sin sacrificar la facilidad de uso. Yo lo uso yo constantemente para trabajar con grandes gráficos.

Respondida el 27/11/2010 a las 15:10
fuente por usuario

votos
6

Como ya se mencionó, NetworkX es muy bueno, con otra opción es igraph . Ambos módulos tendrán la mayoría (si no todas) las herramientas de análisis que probablemente necesite, y ambas bibliotecas se usan de forma rutinaria con redes grandes.

Respondida el 27/08/2008 a las 11:01
fuente por usuario

votos
4

Un diccionario también puede contener gastos generales, dependiendo de la implementación real. Por lo general, una tabla hash contiene un número primo de nodos disponibles para empezar, aunque solo use un par de nodos.

A juzgar por su ejemplo, "Propiedad", ¿sería mejor con un enfoque de clase para el nivel final y las propiedades reales? ¿O los nombres de las propiedades cambian mucho de un nodo a otro?

Diría que lo que significa "eficiente" depende de muchas cosas, como:

  • velocidad de las actualizaciones (insertar, actualizar, eliminar)
  • velocidad de recuperación de acceso aleatorio
  • velocidad de recuperación secuencial
  • memoria usada

Creo que encontrará que una estructura de datos que es rápida generalmente consumirá más memoria que una que sea lenta. Este no es siempre el caso, pero la mayoría de las estructuras de datos parece seguir esto.

Un diccionario puede ser fácil de usar y le brinda un acceso relativamente uniformemente rápido, lo más probable es que use más memoria que, como usted sugiere, enumera. Las listas, sin embargo, generalmente tienden a contener más sobrecarga al insertar datos en ella, a menos que preasignen los nodos X, en los que volverán a usar más memoria.

Mi sugerencia, en general, sería simplemente utilizar el método que parezca más natural para usted, y luego hacer una "prueba de estrés" del sistema, agregarle una cantidad sustancial de datos y ver si se convierte en un problema.

También podría considerar agregar una capa de abstracción a su sistema, para que no tenga que cambiar la interfaz de programación si posteriormente necesita cambiar la estructura interna de datos.

Respondida el 04/08/2008 a las 13:09
fuente por usuario

votos
3

Según tengo entendido, el acceso aleatorio es en tiempo constante tanto para los dictados como para las listas de Python, la diferencia es que solo se puede hacer un acceso aleatorio de índices enteros con listas. Supongo que necesita buscar un nodo por su etiqueta, por lo que quiere un dictado de dicts.

Sin embargo, en el frente de rendimiento, cargarlo en la memoria puede no ser un problema, pero si usa demasiado terminará cambiando a disco, lo que matará el rendimiento de incluso los dictados altamente eficientes de Python. Trate de reducir el uso de memoria tanto como sea posible. Además, la RAM es increíblemente barata en este momento; Si haces este tipo de cosas mucho, no hay razón para no tener al menos 4 GB.

Si desea obtener consejos para reducir el uso de memoria, proporcione más información sobre el tipo de información que está rastreando para cada nodo.

Respondida el 06/08/2008 a las 06:37
fuente por usuario

votos
2

Hacer una estructura basada en clases probablemente tendría más sobrecarga que la estructura basada en dictos, ya que en las clases de python realmente se usan dictados cuando se implementan.

Respondida el 04/08/2008 a las 13:41
fuente por usuario

votos
1

No hay duda de NetworkX es la mejor estructura de datos hasta ahora para el gráfico. Viene con utilidades como funciones auxiliares, estructuras de datos y algoritmos, generadores de secuencias al azar, decoradores, Cuthill-Mckee pedidos, gestores de contexto

NetworkX es grande porque wowrs para los gráficos, dígrafos, y multigrafos. Se puede escribir gráfica con múltiples formas: lista de adyacencia, Multilínea lista de adyacencia, lista de aristas, GEXF, GML. Funciona con salmuera, GraphML, JSON, SparseGraph6 etc.

Tiene implimentation de diversos algoritmos radimade incluyendo: aproximación, bipartito, Límite, Centralidad, Camarilla, Clustering, colorear, Componentes, Conectividad, Ciclos, Dirigido acíclicos gráficos, medidas de distancias, conjunto dominante, euleriano, isomorfismo, Análisis de Enlace, Enlace predicción, Matching , árbol de expansión mínima, Rich club, rutas más cortas, Transversal, Árbol.

Respondida el 18/01/2016 a las 06:08
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more