graph - utilizar - Tres formas de almacenar un gráfico en memoria, ventajas y desventajas

ventajas y desventajas de las graficas de dispersion

Question

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 borde 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?

Answer 1

Creo que su primer ejemplo es un poco ambiguo: nodos como objetos y bordes como punteros. Puede hacer un seguimiento de estos almacenando solo un puntero a algún nodo raíz, en cuyo caso el acceso a un nodo dado puede ser ineficiente (digamos que quiere el nodo 4; si no se proporciona el objeto nodo, puede que tenga que buscarlo) . En este caso, también perderá partes del gráfico que no son alcanzables desde el nodo raíz. Creo que este es el caso que f64 rainbow está asumiendo cuando dice que la complejidad del 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 O (1) acceso a un nodo dado, pero aumenta el uso de la memoria un poco. Si n es el número de nodos y e es el número de bordes, la complejidad del espacio de este enfoque sería O (n + e).

La complejidad del espacio para el enfoque de la matriz sería a lo largo de las líneas de O (n ^ 2) (suponiendo que los bordes son unidireccionales). Si su gráfica es escasa, tendrá muchas celdas vacías en su matriz. Pero si su gráfica está completamente conectada (e = n ^ 2), esto se compara favorablemente con la primera aproximación. Como dice RG, también puede tener menos errores de caché con este enfoque si asigna la matriz como un pedazo de memoria, lo que podría hacer que el seguimiento de una gran cantidad de bordes alrededor del gráfico sea más rápido.

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

Answer 2

De acuerdo, entonces 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 realmente, 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 engatusarlos en un solo trozo de memoria también puede ser un buen plan o cualquier otro método para mantenerlos juntos.

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

Invertir un gráfico dirigido es fácil con la representación de la matriz, y fácil con la lista de adyacencia, pero no tan bueno con la representación del objeto / puntero.

Answer 3

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

Answer 4

El método de objetos y punteros sufre de dificultad de búsqueda, como algunos han señalado, pero son bastante naturales para hacer cosas como construir árboles de búsqueda binarios, donde hay mucha estructura extra.

Personalmente me encantan las matrices de adyacencia porque hacen mucho más fácil todo tipo de problemas, utilizando herramientas de la teoría de grafos algebraicos. (La potencia k de la matriz de adyacencia da el número de caminos de longitud k desde el vértice i hasta el vértice j, por ejemplo. Agregue una matriz de identidad antes de tomar la potencia k para obtener el número de caminos de longitud <= k. n-1 menor del Laplaciano para obtener el número de árboles que se extienden ... Y así sucesivamente).

¡Pero todos dicen que las matrices de adyacencia son costosas para la memoria! Solo tienen la mitad de la razón: puedes evitar esto usando matrices dispersas cuando tu gráfica tiene pocos bordes. Las estructuras de datos de matriz dispersa hacen exactamente el trabajo de solo mantener una lista de adyacencia, pero aún tienen la gama completa de operaciones de matriz estándar disponibles, que le ofrecen lo mejor de ambos mundos.

Answer 5

Hay otra opción: nodos como objetos, bordes como objetos, cada borde al mismo tiempo en dos listas doblemente vinculadas: la lista de todos los bordes que salen del mismo nodo y la lista de todos los bordes que van al 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

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

La estructura también puede representar un gráfico bastante general: multigrafo 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 x a x).

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

Answer 6

Un par de cosas más a considerar:

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

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 volverse no sincronizados.

Answer 7

Una forma de analizarlos es en términos de complejidad de memoria y tiempo (que depende de cómo quiera 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 tiene. El número de punteros (a nodos) requerido es hasta O (n ^ 2) ya que cada objeto 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.

Almacenar una matriz de pesas de borde

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

Según el algoritmo que ejecute en el gráfico y la cantidad de nodos que tenga, tendrá que elegir una representación adecuada.