Recorrido de grafos de memoria externa

El recorrido de grafos de memoria externa es un tipo de recorrido de grafos optimizado para acceder a la memoria almacenada externamente.

El recorrido de grafos es una subrutina en la mayoría de los algoritmos de grafos. El objetivo de un algoritmo de recorrido de grafos es visitar (y/o procesar) cada nodo del grafo. Los algoritmos de recorrido de grafos, como la búsqueda en amplitud y la búsqueda en profundidad , se analizan utilizando el modelo de von Neumann , que asume un coste de acceso a la memoria uniforme. Esta perspectiva ignora el hecho de que, para instancias muy grandes, parte del grafo reside en el disco en lugar de en la memoria interna. Dado que el acceso al disco es mucho más lento que el acceso a la memoria interna, existe la necesidad de un recorrido eficiente de la memoria externa .

Para los algoritmos de memoria externa, se utiliza el modelo de memoria externa de Aggarwal y Vitter ^{[ 1 ]} para el análisis. Una máquina se especifica mediante tres parámetros: M , B y D. M es el tamaño de la memoria interna, B es el tamaño del bloque de un disco y D es el número de discos paralelos. La medida del rendimiento de un algoritmo de memoria externa es el número de operaciones de entrada/salida que realiza.

El algoritmo de búsqueda en anchura comienza en un nodo raíz y recorre todos los nodos hasta una profundidad de uno. Si no quedan nodos sin visitar en la profundidad actual, se recorren los nodos de mayor profundidad. Finalmente, se habrán visitado todos los nodos del grafo.

Munagala y Ranade

Para un grafo no dirigido${\displaystyle G}$Munagala y Ranade ^{[ 2 ]} propusieron el siguiente algoritmo de memoria externa:

Dejar${\displaystyle L(t)}$denotemos los nodos en el nivel de búsqueda en amplitud t y sea${\displaystyle A(t):=N(L(t-1))}$sea ​​el multiconjunto de vecinos de nivel t-1. Para cada t,${\displaystyle L(t)}$se puede construir a partir de${\displaystyle A(t)}$transformándolo en un conjunto y excluyendo de él los nodos visitados previamente.

1. Crear${\displaystyle A(t)}$accediendo a la lista de adyacencia de cada vértice en${\displaystyle L(t-1)}$Este paso requiere${\displaystyle O(|L(t-1)|+|A(t)|/(D\cdot B))}$E/S.
2. Próximo${\displaystyle A'(t)}$se crea a partir de${\displaystyle A(t)}$eliminando duplicados. Esto se puede lograr mediante la ordenación de${\displaystyle A(t)}$, seguido de una fase de escaneo y compactación que requiere${\displaystyle O(\operatorname {sort} (|A|))}$E/S.
3. ${\displaystyle L(t):=A'(t)\backslash \{L(t-1)\cup L(t-2)\}}$se calcula mediante un escaneo paralelo sobre${\displaystyle L(t-1)}$y${\displaystyle L(t-2)}$y requiere${\displaystyle O((|A(t)|+|L(t-1)|+|L(t-2)|)/(D\cdot B))}$E/S.

El número total de E/S de este algoritmo sigue teniendo en cuenta que${\displaystyle \sum _{t}|A(t)|=O(m)}$y${\displaystyle \sum _{t}|L(t)|=O(n)}$y es${\displaystyle O(n+\operatorname {sort} (n+m))}$.

En la figura de la derecha se muestra una representación visual de los tres pasos descritos necesarios para calcular L ( t ).

El algoritmo de búsqueda en profundidad explora un grafo a lo largo de cada rama hasta la mayor profundidad posible, antes de realizar el rastreo inverso.

Para grafos dirigidos , Buchsbaum, Goldwasser, Venkatasubramanian y Westbrook ^{[ 4 ]} propusieron un algoritmo con${\displaystyle O((V+E/B)\log _{2}(V/B)+\operatorname {sort} (E))}$E/S.

Este algoritmo se basa en una estructura de datos llamada árbol de repositorio con búfer (BRT). Almacena un conjunto múltiple de elementos de un universo ordenado. Los elementos se identifican mediante una clave. Un BRT ofrece dos operaciones:

• insert(T, x), que agrega el elemento x a T y necesita${\displaystyle O(1/B\log _{2}(N/B))}$E/S amortizadas. N es el número de elementos añadidos al BTR.
• extract(T, k), que informa y elimina de T todos los elementos con clave k . Requiere${\displaystyle O(\log _{2}(N/B)+S/B)}$E/S, donde S es el tamaño del conjunto devuelto por extract .

El algoritmo simula un algoritmo interno de búsqueda en profundidad. Se mantiene una pila S de nodos. Durante una iteración para el nodo v en la parte superior de S , se agrega un vecino no visitado a S y se continúa la iteración. Si no hay vecinos no visitados, se elimina v .

La dificultad radica en determinar si un nodo no ha sido visitado sin realizar ninguna acción.${\displaystyle \Omega (1)}$E/S por arista. Para hacer esto para un nodo v aristas entrantes ⁠${\displaystyle (x,v)}$Los nodos se colocan en un BRT D cuando v se descubre por primera vez. Además, los nodos salientes ( v , x ) se colocan en una cola de prioridad P ( v ), indexada por el rango en la lista de adyacencia.

Para el vértice u en la parte superior de S, se extraen todas las aristas ( u , x ) de D. Dichas aristas solo existen si x se ha descubierto desde la última vez que u estuvo en la parte superior de S (o desde el inicio del algoritmo si u es la primera vez que está en la parte superior de S ). Para cada arista ( u , x ) se realiza una operación delete( x ) en P ( u ). Finalmente, se realiza una operación delete- min en${\displaystyle P(u)}$⁠ devuelve el siguiente nodo no visitado. Si P ( u ) está vacío, u se extrae de S .

A continuación se muestra el pseudocódigo de este algoritmo.

1 procedimiento BGVW-depth-first-search( G , v ): 2. Sea S una pila, P [] una cola de prioridad para cada nodo y D un BRT. 3 S .push( v ) 4 mientras S no esté vacío: 5 v := S .top() 6 si v no está marcado: 7 marcas ( v ) 8 extraer todas las aristas (v, x) de D , ∀ x : P [ v ].delete( x ) 9 si ( u := P [ v ].delete-min()) no es nulo: 10 S .push( u ) 11 más : 12 S .pop() 13. Marca de procedimiento ( v ) 14 poner todas las aristas ( x , v ) en D 15 ∀ ( v , x ): poner x en P [ v ]