Cuando hablamos de grafos dinámicos (aquellos grafos que cambian sus propiedades con el tiempo) podemos hablar de los investigadores más citados en el campo. Los estudios de Geetha Ramalingam y Thomas William Reps sobre grafos dinámicos en 1996 han servido de bases para muchos algoritmos de hoy. En esta entrada hablaremos solo de su algoritmo incremental para grafos con actualización de arco.

Cuando se habla de algoritmo incremental se refiere a aquellos algoritmos cuyos valores de entrada van cambiando con el tiempo, un problema dinámico.

Actualización de Arco de SSSP

Tenemos un grafo $G$ la cual sufre una actualización en uno de sus arcos, lo denotaremos como $(u, v, w'(u,v))$ donde $u$ y $v$ son vértices (o nodos) del grafo y $w'(u, v)$ es el nuevo valor ponderado de este arco. Tenemos un vértice $s$ el cual queremos encontrar todas las distancias de este vértice fuente a todos los demás vértices, denotamos esta distancia como $d'(s,\cdot )$ . Se definen todos los vértices $t \in V$ tal que $d'(s,t)<d(s,t)$ como los novértices destino afectados. Las actualizaciones se hacen entonces: $d'(s, t) = d(s, u)+w'(u, v) + d(v, t)$ . Así que lo único que se necesita para actualizar es la información en $d'(s,\cdot )$ para encontrar $d'(s, t )$ para los vértices afectados por $d(v, t )$ .

El algoritmo propuesto por RR en Python 3.5 es:

def dijkstra_truncated(self, dist_s):
    u = self.last_vertex_modified[0]
    v = self.last_vertex_modified[1]
    w_uv = self.last_vertex_modified[2]

    dist_s = np.array(dist_s)
    if dist_s[self.vertex == v] <= dist_s[self.vertex == u] + w_uv:
        return

    dist_s[self.vertex == v] = dist_s[self.vertex == u] + w_uv
    PQ = {v: dist_s[v]}

    while len(PQ) > 0:
        (y, weight) = min(PQ.items(), key=lambda x: x[1])
        PQ.pop(y)
        for w in self.target[self.source == y]:
            if dist_s[self.vertex == w] <= weight + self.get_weight(y, w):
                continue

            new_weight = weight + self.get_weight(y, w)
            dist_s[self.vertex == w] = new_weight
            PQ[w] = new_weight

    return dist_s

El algoritmo basicamente es como Dijkstra rotando en $v$ , la diferencia es que solo los vértices afectados entran en la cola de prioridad. En el algoritmo la cola de prioridad es la variable PQ. Podemos probar la velocidad de este algoritmo si, después de una actualización de arco, ejecutamos el dijkstra y el algoritmo SSSP de RR. El algoritmo fue editamo de manera que no recibe cualquier vértice fuente, más bien el vértice fuente es aquel que se actualiza.

Tenemos el grafo:

Source:  [1 0 3 2 1 4 5 4 3 5]
Target:  [0 2 0 1 3 1 1 3 5 4]
Weight:  [2 2 4 3 2 4 4 3 5 1]
Vertex:  [0 1 2 3 4 5]

Figura 1. Grafo incremental para prueba. Arco actualizado (1, 3)

El arco actualizado es (1, 3) antes pesaba 2, ahora pesa 1 unidad.

Tomamos entonces el vértice [1] como el vértice fuente. El SSSp de el vértice fuente antes de la actualzación era:

[  2.  0.  4.  2.  8.  7.]

Cada elemento del array anterior representa la distancia más corta del vértice fuente ([1]) a cada vértice del grafo: [0 1 2 3 4 5] respectivamente.

mean_time_dijkstra_sp = 0
for times1 in range(num_tries):
    t = time()
    graph.sssp_dijkstra(source)
    lapsed = time() - t
    mean_time_dijkstra_sp = mean_time_dijkstra_sp + lapsed
mean_time_dijkstra_sp = mean_time_dijkstra_sp / num_tries

El anterior algoritmo corre el Dijkstra varias veces y promedia los resultados. Hacemos lo mismo para el algoritmo de RR:

mean_time_rr_sp = 0
for times2 in range(num_tries):
    t = time()
    graph.dijkstra_truncated(dist.tolist())
    lapsed = time() - t
    mean_time_rr_sp = mean_time_rr_sp + lapsed
mean_time_rr_sp = mean_time_rr_sp / num_tri

Para ambos la solución del SSSP y su tiempo son:

[ 2.  0.  4.  1.  7.  6.]

SSSP Dijkstra:  0.0005824699401855469
SSSP RR      :  0.00013216471672058107
Is less? True

Podemos decir que el tiempo de ejecución para RR es menor en SSSP.

El código de esta prueba se encuentra en mi repositorio público, el archivo es: https://github.com/arturoverbel/graph_python/blob/master/full_test_RR_sssp.py

Actualización de Arco para APSP

Bueno, para encontrar el APSP basta con correr el algoritmo anterior por cada vértice para obtener una solución rápida, sin embargo RR proponen un nuevo algoritmo para otimizar el tiempo de respuesta. Según las pruebas (más abajo se encuentran) el tiempo es menor que correr un algoritmo como Floyd-Warshall. Ramalingam y Reps nos muestra una manera mejor para resolverlo. Si ya sabemos los vértices destino que posee nuestro vértice fuente por la actualización, entonces estos vértices destino los agregamos como fuente en otro cola. Para esto se utiliza un código BFS (Breadth- First Search, algoritmo para búsqueda en árboles) en Dijkstra. El código en Python 3.5:

def bfs_truncated(self, source, dist):
    u = self.last_vertex_modified[0]
    v = self.last_vertex_modified[1]
    w_uv = self.last_vertex_modified[2]

    dist = np.array(dist)
    if dist[self.vertex == source, self.vertex == v] <= dist[self.vertex == source, self.vertex == u] + w_uv:
        return dist

    dist[self.vertex == source, self.vertex == v] = dist[self.vertex == source, self.vertex == v] + w_uv

    PQ = np.array([v])
    vis = {v: True}

    while len(PQ) > 0:
        y, PQ = PQ[-1], PQ[:-1]
        dist[self.vertex == source, self.vertex == y] = dist[self.vertex == source, self.vertex == u] + w_uv + dist[self.vertex == v, self.vertex == y]
        for w in self.target[self.source == y]:
            if (w not in vis or not vis[w]) \
                    and dist[self.vertex == source, self.vertex == w] > dist[self.vertex == source, self.vertex == u] + w_uv + dist[self.vertex == v, self.vertex == w]:
                vis[w] = True
                PQ = np.append(PQ, [w])

Esta versión actualiza el algoritmo SSSP. En la línea 20 vemos que solo analizamos solo aquellos que cumplen la condición $d'(s, v) > d'(s, v)$ , equivalente a $d(s, v) > d(s, u) + w'(u, v)$ . Aquellos que cumpla esta condición son los que tenemos que actualizar algo. Hasta aquí solo actualizamos los vértices desde el vértice objetivo de la actualización, en el ejemplo anterior los nodos que se deberían actualizar con este método sería: [1] y [3], el vértice [0] no tiene arcos salientes.

Ahora para los nodos que llegan al nodo [1] también deberían actualizarse, en este ejemplo sería los vértices [2] y [0], los demás vértices que llegan a [1] no se actualizaría. Para esto corremos otro algoritmo para detectar que nodos son afectados:

def find_source_affected(self, dist):
    dist = np.array(dist)
    u = self.last_vertex_modified[0]
    v = self.last_vertex_modified[1]
    w_uv = self.last_vertex_modified[2]

    source_affected = np.array([])
    dist = np.array(dist)
    if dist[self.vertex == u, self.vertex == v] <= w_uv + [0]:
        return source_affected

    dist[self.vertex == u, self.vertex == v] = dist[self.vertex == u, self.vertex == v] + w_uv

    PQ = np.array([v])
    vis = {v: True}

    while len(PQ) > 0:
        x, PQ = PQ[-1], PQ[:-1]
        for z in self.source[self.target == x]:
            if (z not in vis or not vis[z]) \
                    and dist[self.vertex == z, self.vertex == v] > \
                    dist[self.vertex == z, self.vertex == u] + w_uv:
                vis[z] = True
                PQ = np.append(PQ, [z])
                source_affected = np.append(source_affected, [z])

    return source_affected

el algoritmo anterior complementa el BFS truncado de manera que identifica que nodos son afectados, que llegan al nodo fuente de la actualización. La idea de estos algoritmos es completar el APSP de actualización de arco corriendo primero el algoritmo para detectar los nodos afectados y luego el BFS.

Tomando como base el grafo de la figura 1, podemos correr varias veces el algoritmo de Floyd-Warshall para promediar su tiempo de respuesta y luego corremos el APSP de RR.

print("------- Floyd -Warshall after Update -----")

dist_fw = graph.floyd_warshall()
print(dist_fw)
mean_time_fw = 0
for times1 in range(num_tries):
    t = time()
    graph.floyd_warshall()
    lapsed = time() - t
    mean_time_fw = mean_time_fw + lapsed
mean_time_fw = mean_time_fw / num_tries
print('Time: ', mean_time_fw)

dist_rr = graph.bfs_truncated_with_sources(dist.tolist())
print(dist_rr)
mean_bfs_truncated_only_sources = 0
for times1 in range(num_tries):
    t = time()
    graph.bfs_truncated_with_sources(dist.tolist())
    lapsed = time() - t
    mean_bfs_truncated_only_sources = mean_bfs_truncated_only_sources + lapsed
mean_bfs_truncated_only_sources = mean_bfs_truncated_only_sources / num_tries
print('Time: ', mean_bfs_truncated_only_sources)

Tenemso como respuesta:

------- Result before update -----
[[  0.   5.   2.   7.  13.  12.]
 [  2.   0.   4.   2.   8.   7.]
 [  5.   3.   0.   5.  11.  10.]
 [  4.   9.   6.   0.   6.   5.]
 [  6.   4.   8.   3.   0.   8.]
 [  6.   4.   8.   4.   1.   0.]]

------- Floyd -Warshall after Update -----
[[  0.   5.   2.   6.  12.  11.]
 [  2.   0.   4.   1.   7.   6.]
 [  5.   3.   0.   4.  10.   9.]
 [  4.   9.   6.   0.   6.   5.]
 [  6.   4.   8.   3.   0.   8.]
 [  6.   4.   8.   4.   1.   0.]]
Time:  0.0025981102705001833

------- BFS truncated (only source affected)-----
[ 1.  2.  0.]
[[  0.   5.   2.   6.  12.  11.]
 [  2.   0.   4.   1.   7.   6.]
 [  5.   3.   0.   4.  10.   9.]
 [  4.   9.   6.   0.   6.   5.]
 [  6.   4.   8.   3.   0.   8.]
 [  6.   4.   8.   4.   1.   0.]]
Time:  0.0010366994142532349

Podemos observar que el algoritmo de RR es ligeramente menor que el algoritmo de Floyd-Warshall en tiempos.

Comparación de algoritmos

Para la comparación de algoritmos se realiza una clase de prueba similiar al que vimos a la entrada anterior: Algoritmos de Dijkstra y Floyd-Warshall en Python 3.5. El cual calcula el tiempo de resolver el APSP en diferentes grafos aleatorios, se va subiendo el número de nodos de grafos y se comparan con una gráfica. Esta vez colocamos una probabilidad del 90% de que existan arcos entre los vértices.

El resultado:

Figura 2. Tiempo de algoritmo de Floyd-Warshall con el de RR en APSP

Los tiempos de FW son los puntos y el de RR son las lineas. Es evidente que el algoritmo de RR es mucho mejor que el algoritmo de FW en el cálculo de APSP para actualización incremental de arco.

Anexos

El repositorio público de este proyecto es: https://github.com/arturoverbel/graph_python donde:

Algoritmos de Ramalingam y Reps: https://github.com/arturoverbel/graph_python/blob/master/_graph/GraphRR.py
Prueba SSSP con grafo definido: https://github.com/arturoverbel/graph_python/blob/master/full_test_RR_sssp.py
Prueba APSP con grafo definido: https://github.com/arturoverbel/graph_python/blob/master/test_dynamic_RR_apsp.py
Prueba con grafos aleatorios: https://github.com/arturoverbel/graph_python/blob/master/test_many_dynamic_incremental.py

Fuentes

On the computational complexity of dynamic graph algorithms

Mi Camino Master

Mi experiencia y mis pensamientos acerca de mis estudios de Maestría en Ciencias de la Información y las Comunicaciones

Algoritmo incremental de Ramalingam y Reps

Actualización de Arco de SSSP

Actualización de Arco para APSP

Comparación de algoritmos

Anexos

Fuentes

Arturo Verbel De Leon

0 Comments

Add yours

3 Pingbacks

Comentarios Cancel reply

Lo más visto

Sígueme

Lo más visto

Últimas entradas

Sígueme