Existen múltiples algoritmos para calcular el APSP de un grafo dinámico incremental. Un grafo dinámico incremental es aquel que dado una actualización del grafo (insertar un nuevo arco o disminuir el peso de un arco), este disminuye el peso de algunos caminos de un nodo a otro. APSP es un problema de la teoría de grafos y consiste en calcular los caminos más cortos para todos los pares de nodos.

Los algoritmos que resuelven problemas de grafos dinámicos incrementales se conocen como algoritmos incrementales. En este blog hemos presentado algunos, tales como Algoritmo incremental de Ramalingam y Reps y librerías de grafos para trabajar esta propiedad de los grafos (Librería de Grafos dinámicos -Python 3).

En esta ocasión les comparto cómo realizar un escenario de peor caso para un algoritmo incremental y ver cuánto se demora en resolverlo. El peor esenario de un algoritmo incremental puede ser:

  • Para un nuevo arco, es el producto mayor entre los predecesores del nodo inicial y los sucesores del nodo final.
  • Para disminución de un arco, es el producto mayor entre los predecesores del nodo inicial y los sucesores del nodo final de entre los pares de nodos (lista de arcos)

Algoritmo para encontrar nodos predecesores y sucesores

Para encontrar nodos predecesores nos basamos en código de Ramalingam y Reps para encontrarlos:

def find_total(self, node):
    sources = 0
    vis = [False for i in self.nodes]
    Q = deque([node])
    vis[node] = True

    while len(Q) > 0:
        x = Q.popleft()

        list = self.source[self.target == x] 

        for z in list:
            if not vis[z]:
                vis[z] = True
                Q.append(z)
                sources += 1

    return sources

En este código solo nos interesa saber cuántos predecesores tiene, por eso se devuelve la variable sources que es un entero. Este algoritmo encuentra los predecesores de un nodo de varios niveles.

Para hacerlo más abierto a nuestro código, se le añade un nuevo argumento que permita elegir entre predecesores y sucesores de un nodo, en el código a continuación:

def find_total(self, node, to_find="sources"):
    sources = 0
    vis = [False for i in self.nodes]
    Q = deque([node])
    vis[node] = True

    while len(Q) > 0:
        x = Q.popleft()

        list = self.source[self.target == x] if to_find == 'sources' else self.target[self.source == x]

        for z in list:
            if not vis[z]:
                vis[z] = True
                Q.append(z)
                sources += 1

    return sources

Algoritmo para encontrar un nuevo arco entre nodos

Para insertar un nuevo arco necesitamos saber el total de todos los predecesores y sucesores de cara nodo y sacar las cuentas. Para eso hacemos un simple ciclo:

node_sources = {}
node_targets = {}
for node in self.nodes:
    node_sources[node] = self.find_total(node, "sources")
    node_targets[node] = self.find_total(node, "targets")

Almacenamos todos estos valores y luego calculamos entre cada par de nodos cuál posee el mayor producto con el siguiente código:

max_path_long = 0
node_source = 0
node_target = 0
for x in self.nodes:
    for y in self.nodes:
        if x == y:
            continue

        if self.get_weight(x, y) != np.inf:
            continue

        total_path_long = node_sources[x] * node_targets[y]
        if total_path_long > max_path_long:
            max_path_long = total_path_long
            node_source = x
            node_target = y

return {
    "source": node_source,
    "target": node_target
}

La linea 10 nos ayuda a eliminar aquellos nodos que no poseen un arco, utilizando la función de la librería. La linea 13 calculamos el producto entre los predecesores y sucesores entre los nodos e inmediatamente verificamos si es el mayor de los que hemos evaluado en la iteración. Las variables resultantes son node_source y node_target.

Por último agregamos el código en la librería de esta manera:

def insert_worst_edge(self, weight=1):
    self.clean_vars()

    result_found = self.find_source_target_worst_scenary_incremental_edge()
    source = result_found['source']
    target = result_found['target']

    return self.insert_edge(source, target, weight)

Las cuales la función find_source_target_worst_scenary_incremental_edge() es la que acabamos de implementar. insert_edge(source, target, weight) es de nuestra librería y solo inserta un edge dado al grafo.

Algoritmo para encontrar un nuevo arco entre nodos

Utilizaremos la función anterior para encontrar los sucesores de un nodo. El algoritmo para encontrar el arco de peor caso será parecido al algoritmo anterior:

node_sources = {}
node_targets = {}
for node in self.nodes:
    node_sources[node] = self.find_total(node, "sources")
    node_targets[node] = self.find_total(node, "targets")

max_path_long = 0
node_source = 0
node_target = 0
for x in self.nodes:
    for y in self.nodes:
        if x == y:
            continue

        if self.get_weight(x, y) == np.inf:
            continue

        total_path_long = node_sources[x] + node_targets[y]
        if total_path_long > max_path_long:
            max_path_long = total_path_long
            node_source = x
            node_target = y

return {
    "source": node_source,
    "target": node_target
}

En la linea 15 hacemos la validación de que el par de nodos tengan un arco entre si.

Testing

El script a continuación generamos un grafo, llamamos a la función de insert_worst para imprimir el resultado:

import os
import sys
import numpy as np

myPath = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, myPath + '/../')

from graph.Graph import Graph
from algorithms.floyd_warshall import *
from algorithms.quinca import *

sources = [0, 2, 2, 3, 4, 4, 5]
targets = [4, 0, 4, 5, 0, 3, 4]
weights = [3, 5, 5, 9, 9, 4, 8]

graph = Graph(sources, targets, weights)
graph.print_r()
print("Insert Worst Edge")

graph.insert_worst_edge()
graph.print_r()
print(graph.last_edge_updated)

El cual puede ser consultado en mi repositorio personal: https://github.com/arturoverbel/graph_presentation/blob/master/scripts/graph_worst.py

El resultado en consola es:

Source:  [0 2 2 3 3 4 5]
Target:  [4 0 4 5 1 3 4]
Weight:  [3 5 5 9 8 4 8]
Vertex:  [0 1 2 3 4 5]
Insert Worst Edge
{0: 1, 1: 5, 2: 0, 3: 4, 4: 4, 5: 4}
{0: 4, 1: 0, 2: 5, 3: 3, 4: 3, 5: 3}
Source:  [0 1 2 2 3 3 4 5]
Target:  [4 2 0 4 5 1 3 4]
Weight:  [3 1 5 5 9 8 4 8]
Vertex:  [0 1 2 3 4 5]
[1 2 1]
.

El grafo antes de la inserción es:

Grafo antes de la actualización

 

Si hacemos una tabla para ver los sucesores y antecesores de cada nodo tenemos:

Nodos 0 1 2 3 4 5
número nodos Antecesores 1 5 0 4 4 4
número nodos Sucesores 4 0 5 3 3 3

Vemos que el nodo 1 y el nodo 2 son candidatos perfectos.

Código

Insertar arco de peor escenario para algoritmos incrementales:

https://github.com/arturoverbel/graph_presentation/blob/master/graph/DynamicGraph.py#L223

Actualizar arco de peor escenario para algoritmos incrementales:

https://github.com/arturoverbel/graph_presentation/blob/master/graph/DynamicGraph.py#L254

Script para prueba:

https://github.com/arturoverbel/graph_presentation/blob/master/scripts/graph_worst.py