Cómo evitar "spaghetti puntero montón" en gráficos dinámicos?

Puede ver esto en términos de recolección de basura halfspace. Esto no es difícil de implementar (lo he hecho para un intérprete), especialmente porque solo lo estás haciendo para estructuras de nodos de tamaño fijo. Asigne de un bloque grande (llamado halfspace) de la memoria. Cuando esté demasiado lleno o fragmentado, detente y copia todo al otro (que también puedes hacer más grande). El truco es actualizar todos los punteros. Para esto hay un algoritmo muy elegante y eficiente llamado scan copy. Hay una buena discusión de ello en Cornell. Esencialmente atraviesa la anchura del gráfico primero, copiando a medida que avanza, sin ningún espacio adicional que no sea lo que está copiando. Una buena propiedad del algoritmo es que los primeros niveles de amplitud terminan adyacentes después de cada copia. Si este es un nivel suficientemente bueno de localidad, lo obtendrá de manera muy eficiente con este método.

Si realmente te preocupa el diseño de la memoria, puede que valga la pena manejarlo tú mismo.

Puede malloc un gran bloque de memoria al inicio, luego asigna espacio desde ese bloque. Necesitará una estructura separada para realizar un seguimiento de lo que se ha asignado y lo que no se ha asignado. Si sabe que todas las estructuras asignadas son de un cierto tamaño que puede simplificar la administración del espacio asignado/libre, es decir, una matriz de índices, de lo contrario, podría usar una lista vinculada de punteros en el espacio libre. Dado que es probable que esté asignando estructuras de una en una, probablemente no tenga que preocuparse por realizar un seguimiento del bloque contiguo más pequeño y/o más grande de espacio libre.

Una cosa de la que tendrás que tener cuidado es la alineación. Una vez más, si siempre va a asignar memoria en múltiplos del tamaño de una sola estructura, que hace las cosas más fáciles, de lo contrario es probablemente una buena idea para asegurarse de que todas las asignaciones comienzan en un límite de 4 bytes, es decir, la diferencia entre la dirección que asigna y la dirección de inicio recibida de malloc hay un múltiplo de 4.

Puede pasar parámetros adicionales a sus funciones de asignación personalizadas para dar pistas sobre dónde debe colocarse el bloque, como la dirección de uno o más nodos cercanos.

Esto se puede ver como un problema de partición de gráficos , donde está tratando de agrupar nodos de gráficos vinculados en el mismo bloque de memoria. METIS es un buen algoritmo de partición de gráficos que probablemente no sea apropiado para su caso de uso porque requiere operaciones globales en todo el gráfico, sin embargo, dos algoritmos de partición de gráficos distribuidos que pueden modificarse para ser aplicables a su caso de uso son DIDIC y Ja-Be-Ja - los primeros intentos de minimice el número de bordes que cruzan particiones sin tener en cuenta el tamaño de la partición, mientras que este último intenta crear particiones de igual tamaño. Ambos algoritmos solo requieren conocimiento local del gráfico para agrupar cada nodo, por lo que si tiene ciclos de repuesto, puede usarlos para reequilibrar el gráfico de forma incremental. Fennel es un algoritmo relacionado que opera en gráficos de transmisión, por lo que, por ejemplo, podría usar Fennel o un algoritmo similar al asignar inicialmente un nodo de gráfico, y luego usar DIDIC / Ja-Be-Ja al reequilibrar el gráfico.