Estructura de datos para almacenar bordes de un gráfico

8

Actualmente estoy trabajando en mi tesis de maestría, y se trata de la agrupación en gráficos. Estoy trabajando con una idea usando hormigas para resolver el problema. Actualmente estoy trabajando en la implementación y me pregunto exactamente qué tan bien representar los bordes del gráfico.

Cada borde se aumenta con cierta información, como su valor de feromona y la cantidad de veces que una hormiga ha visitado ese borde. Trabajaré con gráficos no dirigidos, que pueden llegar a ser bastante grandes (más de un millón de vértices) y me preguntaba cuál es la forma más eficiente para almacenar los bordes y buscarlos. Estaba pensando en apegarme a una convención y almacenar puntos finales de acuerdo con el que tiene una identificación de vértice inferior parav1 y el más alto para v2 (v1 y v2son los puntos finales del borde en la estructura de datos). Pero me pregunto cómo realizaría una búsqueda en este caso.

Se me ocurrió una asignación de la matriz de adyacencia a la matriz de bordes, pero eso solo funciona si el gráfico subyacente es un gráfico completo. Así que vine aquí para obtener algunas sugerencias sobre cómo debería proceder, porque necesito que mi búsqueda sea eficiente y, al mismo tiempo, no quiero volar el espacio de almacenamiento para los bordes, ya que los gráficos serán enormes.

graph-theory data-structures evolutionary-computing lodoso
fuente
1
¿Su gráfico es escaso o denso? Porque la respuesta depende de eso.
Bartosz Przybylski
Oh, debería haber mencionado eso, sí, son en su mayoría gráficos dispersos. Básicamente, los gráficos con los que voy a trabajar representan redes del mundo real que generalmente son dispersas. :)
fangoso
¿Listas de adyacencia ordenadas?
Raphael

Respuestas:

5

Si su gráfico es escaso, entonces debe almacenarlo usando "listas" de adyacencia, aunque probablemente desee algo más eficiente que una lista (o tal vez no, dependiendo del uso). Es más simple si almacena cada borde en ambos puntos finales. Esto se puede implementar de muchas maneras, por ejemplo, puede almacenar todos los datos en una gran matriz y almacenar solo punteros en las "listas" de adyacencia.

Yuval Filmus
fuente
Hasta ahora he estado usando un enfoque de lista de adyacencia donde para cada vértice tengo una matriz de sus vecinos (cada vértice es un objeto). De esta manera ayuda porque cada hormiga conoce a los vecinos de cada vértice. Pero necesito elegir qué borde atravesar a continuación, según la información de feromona y algunos otros datos que calcularé. No quiero introducir duplicación, así que me preguntaba si había una manera de representar cada borde individualmente pero poder indexarlos de manera eficiente al mismo tiempo, ya que necesitaré mucha búsqueda para cada borde en cada iteración .
fangoso
Como ejemplo, aquí está el posible mapeo a los índices de la matriz de borde si el gráfico estaba completo. En este caso, ya sabemos que el tamaño de la matriz de bordes será n (n-1), donde n es el número de vértices. Entonces, para traducir la matriz de adyacencia [x] [y] al índice de matriz (idx) puede ser como sigue: si x <= y entonces idx = n * x - x * (x + 1) / 2 + (y - x - 1) else idx = n * y - y * (y + 1) / 2 + (x - y - 1) Entonces, digamos que edge (5,11) u (11,5) se traducirán al mismo índice de matriz. Pero como no estoy trabajando con gráficos completos, no puedo pensar en un mapeo.
fangoso
2
Sigue insistiendo en usar estructuras de datos que solo tengan sentido para gráficos densos. Para gráficos dispersos, el enfoque siempre es almacenar, de alguna manera, para cada vértice todos los bordes incidentes. No hay duplicación: los datos solo se almacenan en un lugar; pero hay dos punteros a los datos. La indexación rápida podría implementarse utilizando árboles de búsqueda, tablas hash, etc. Estos le permitirán implementarG[x][y]rápido y con suerte sin demasiado espacio encima.
Yuval Filmus