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

Question

Necesito poder manipular un gráfico grande (10 ^ 7 nodos) en Python.Los datos correspondientes a cada nodo/borde son mínimos, digamos, una pequeña cantidad de cadenas.¿Cuál es el más eficiente, en términos de memoria y velocidad, forma de hacer esto?

Un dictado de dictados es más flexible y sencillo 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 lleva mucho tiempo es visitar los nodos para poder 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 gastos generales.Esperaba que alguien tuviera alguna experiencia directa con un caso similar que pudiera compartir.Después de todo, los gráficos son una de las abstracciones más comunes en informática.

Answer 1

Le recomiendo encarecidamente que mire RedX.Es un caballo de guerra probado en batalla y la primera herramienta a la que recurren la mayoría de los tipos de 'investigación' cuando necesitan realizar análisis de datos basados ​​en redes.He manipulado gráficos con cientos de miles de aristas sin problemas en una computadora portátil.Tiene muchas funciones y es muy fácil de usar.Se encontrará concentrándose más en el problema en cuestión que en los detalles de la implementación subyacente.

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

"""
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:

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

Answer 2

Aunque esta pregunta ya es bastante antigua, creo que vale la pena mencionar mi propio módulo de Python para manipulación de gráficos llamado herramienta gráfica.Es muy eficiente, ya que las estructuras de datos y algoritmos se implementan en C++, con metaprogramación de plantillas, utilizando la biblioteca Boost Graph.Por lo tanto, su rendimiento (tanto en uso de memoria como en tiempo de ejecución) es comparable al de una biblioteca C++ pura y puede ser mucho mejor que el código Python típico, sin sacrificar la facilidad de uso.Yo mismo lo uso constantemente para trabajar con gráficos muy grandes.

Answer 3

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

Answer 4

Un diccionario también puede contener gastos generales, según la implementación real.Para empezar, una tabla hash generalmente contiene un número primo de nodos disponibles, aunque solo pueda usar un par de nodos.

A juzgar por su ejemplo, "Propiedad", ¿sería mejor 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?

Yo 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 rápida generalmente consumirá más memoria que una lenta.Este no es siempre el caso, pero la mayoría de las estructuras de datos parecen seguir esto.

Un diccionario puede ser fácil de usar y brindarle un acceso relativamente rápido y uniforme; lo más probable es que utilice más memoria que, como usted sugiere, las listas.Sin embargo, las listas generalmente tienden a contener más sobrecarga cuando se insertan datos en ellas, a menos que preasignen X nodos, en los que nuevamente usarán más memoria.

Mi sugerencia, en general, sería simplemente usar el método que le parezca más natural 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, de modo que no tenga que cambiar la interfaz de programación si luego necesita cambiar la estructura de datos interna.

Answer 5

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 realizar acceso aleatorio a índices enteros con listas.Supongo que necesitas buscar un nodo por su etiqueta, por lo que quieres un dictado de dictados.

Sin embargo, en el frente del rendimiento, cargarlo en la memoria puede no ser un problema, pero si usas demasiado terminarás cambiándolo al disco, lo que acabará con el rendimiento incluso de los altamente eficientes dicts de Python.Intente mantener el uso de memoria lo más bajo posible.Además, la RAM es increíblemente barata en este momento;Si haces este tipo de cosas con frecuencia, no hay razón para no tener al menos 4 GB.

Si desea obtener consejos sobre cómo mantener bajo el uso de la memoria, brinde más información sobre el tipo de información que está rastreando para cada nodo.

Answer 6

Crear una estructura basada en clases probablemente tendría más gastos generales que la estructura basada en dict, ya que en Python las clases en realidad usan dicts cuando se implementan.

Answer 7

Sin duda, NetworkX es la mejor estructura de datos hasta ahora para gráficos.Viene con utilidades como funciones auxiliares, estructuras de datos y algoritmos, generadores de secuencias aleatorias, decoradores, pedidos Cuthill-Mckee y administradores de contexto.

NetworkX es fantástico porque destaca por sus gráficos, dígrafos y multigrafos.Puede escribir gráficos de varias maneras:Lista de adyacencia, Lista de adyacencias de múltiples centrales, lista de borde, GEXF, GML.Funciona con Pickle, GraphML, JSON, SparseGraph6, etc.

Tiene implementación de varios algoritmos radimade que incluyen:Aproximación, bipartito, límite, centralidad, camarilla, agrupación, coloración, componentes, conectividad, ciclos, gráficos acíclicos dirigidos, medidas de distancia, conjuntos dominantes, euleriano, isomorfismo, análisis de enlaces, predicción de enlace, coincidencia, árbol mínimo, club, rico, rico, rico, rico, más corto Caminos, transversal, árbol.