Tres formas de almacenar un gráfico en la memoria, ventajas y desventajas

Hay tres formas de almacenar un gráfico en la memoria:

1. Nodos como objetos y bordes como punteros
2. Una matriz que contiene todos los pesos de los bordes entre el nodo numerado xy el nodo y
3. Una lista de bordes entre nodos numerados

Sé cómo escribir los tres, pero no estoy seguro de haber pensado en todas las ventajas y desventajas de cada uno.

¿Cuáles son las ventajas y desventajas de cada una de estas formas de almacenar un gráfico en la memoria?

Una forma de analizarlos es en términos de complejidad de memoria y tiempo (que depende de cómo desee acceder al gráfico).

Almacenar nodos como objetos con punteros entre sí

• La complejidad de la memoria para este enfoque es O (n) porque tiene tantos objetos como nodos. El número de punteros (a nodos) necesarios es de hasta O (n ^ 2) ya que cada objeto de nodo puede contener punteros para hasta n nodos.
• La complejidad de tiempo para esta estructura de datos es O (n) para acceder a cualquier nodo dado.

Almacenamiento de una matriz de pesos de los bordes

• Esta sería una complejidad de memoria de O (n ^ 2) para la matriz.
• La ventaja de esta estructura de datos es que la complejidad de tiempo para acceder a cualquier nodo dado es O (1).

Dependiendo del algoritmo que ejecute en el gráfico y de cuántos nodos haya, deberá elegir una representación adecuada.

Un par de cosas más para considerar:

1. El modelo matricial se presta más fácilmente a gráficos con bordes ponderados, al almacenar los pesos en la matriz. El modelo de objeto / puntero necesitaría almacenar pesos de borde en una matriz paralela, lo que requiere sincronización con la matriz de puntero.

2. El modelo de objeto / puntero funciona mejor con gráficos dirigidos que con gráficos no dirigidos porque los punteros deberían mantenerse en pares, que pueden desincronizarse.

El método de objetos y punteros presenta dificultades de búsqueda, como algunos han señalado, pero es bastante natural para hacer cosas como construir árboles de búsqueda binarios, donde hay mucha estructura adicional.

Personalmente, me encantan las matrices de adyacencia porque facilitan mucho todo tipo de problemas, utilizando herramientas de la teoría de grafos algebraicos. (La k-ésima potencia de la matriz de adyacencia da el número de caminos de longitud k desde el vértice i al vértice j, por ejemplo. Agregue una matriz de identidad antes de tomar la k-ésima potencia para obtener el número de caminos de longitud <= k. Tome un rango n-1 menor del Laplaciano para obtener el número de árboles de expansión ... Y así sucesivamente.)

¡Pero todo el mundo dice que las matrices de adyacencia cuestan memoria! Son solo la mitad de la derecha: puede solucionar esto usando matrices dispersas cuando su gráfico tiene pocos bordes. Las estructuras de datos matriciales dispersas hacen exactamente el trabajo de simplemente mantener una lista de adyacencia, pero aún tienen la gama completa de operaciones matriciales estándar disponibles, lo que le brinda lo mejor de ambos mundos.

Creo que su primer ejemplo es un poco ambiguo: los nodos como objetos y los bordes como punteros. Puede realizar un seguimiento de estos almacenando solo un puntero a algún nodo raíz, en cuyo caso acceder a un nodo determinado puede ser ineficiente (digamos que desea el nodo 4; si no se proporciona el objeto de nodo, es posible que deba buscarlo) . En este caso, también perdería partes del gráfico a las que no se puede acceder desde el nodo raíz. Creo que este es el caso que asume f64 rainbow cuando dice que la complejidad de tiempo para acceder a un nodo dado es O (n).

De lo contrario, también podría mantener una matriz (o hashmap) llena de punteros a cada nodo. Esto permite el acceso O (1) a un nodo determinado, pero aumenta un poco el uso de memoria. Si n es el número de nodos ye es el número de bordes, la complejidad espacial de este enfoque sería O (n + e).

La complejidad del espacio para el enfoque matricial estaría en las líneas de O (n ^ 2) (asumiendo que los bordes son unidireccionales). Si su gráfico es escaso, tendrá muchas celdas vacías en su matriz. Pero si su gráfico está completamente conectado (e = n ^ 2), esto se compara favorablemente con el primer enfoque. Como dice RG, también puede tener menos fallas de caché con este enfoque si asigna la matriz como una porción de memoria, lo que podría acelerar el seguimiento de muchos bordes alrededor del gráfico.

El tercer enfoque es probablemente el más eficiente en términos de espacio para la mayoría de los casos, O (e), pero haría que encontrar todos los bordes de un nodo dado fuera una tarea O (e). No puedo pensar en un caso en el que esto sea muy útil.

Eche un vistazo a la tabla de comparación en wikipedia. Da una buena comprensión de cuándo usar cada representación de gráficos.

Hay otra opción: los nodos como objetos, los bordes como objetos también, cada borde está al mismo tiempo en dos listas doblemente enlazadas: la lista de todos los bordes que salen del mismo nodo y la lista de todos los bordes que entran en el mismo nodo .

struct Node {
    ... node payload ...
    Edge *first_in;    // All incoming edges
    Edge *first_out;   // All outgoing edges
};

struct Edge {
    ... edge payload ...
    Node *from, *to;
    Edge *prev_in_from, *next_in_from; // dlist of same "from"
    Edge *prev_in_to, *next_in_to;     // dlist of same "to"
};

La sobrecarga de memoria es grande (2 punteros por nodo y 6 punteros por borde) pero obtienes

• Inserción del nodo O (1)
• O (1) inserción de borde (punteros dados a los nodos "desde" y "a")
• O (1) eliminación de borde (dado el puntero)
• Eliminación de nodo O (deg (n)) (dado el puntero)
• O (deg (n)) encontrar vecinos de un nodo

La estructura también puede representar un gráfico bastante general: multigraph orientado con bucles (es decir, puede tener múltiples bordes distintos entre los mismos dos nodos, incluidos múltiples bucles distintos, bordes que van de xa x).

Una explicación más detallada de este enfoque está disponible aquí .

Bien, si los bordes no tienen pesos, la matriz puede ser una matriz binaria, y el uso de operadores binarios puede hacer que las cosas vayan muy, muy rápido en ese caso.

Si el gráfico es escaso, el método de objeto / puntero parece mucho más eficiente. Mantener el objeto / punteros en una estructura de datos específicamente para convencerlos en un solo trozo de memoria también puede ser un buen plan, o cualquier otro método para lograr que permanezcan juntos.

La lista de adyacencia, simplemente una lista de nodos conectados, parece, con mucho, la más eficiente en memoria, pero probablemente también la más lenta.

Revertir un gráfico dirigido es fácil con la representación matricial y fácil con la lista de adyacencia, pero no tan bien con la representación de objeto / puntero.