En anteriores entradas se ha hablado de algoritmo incremental ( Insertar un arco como el peor escenario para calcular el APSP en un grafo dirigido ). Son aquellos algoritmos que resuelven un grafo que ha disminuido sus caminos más cortos (Shortest Path), sea agregando un nuevo arco en el grafo o disminuir un peso en un arco ya existente.

Existen muchos algoritmos que resuelven este problema, pero esta vez les mostraré un algoritmo nuevo que resulta mucho más rápido en ciertas ocasiones:

ABM Algoritmo con predecesor

import numpy as np
from collections import deque

# Affected Block Matriz = ABM Update
def ABM_Update_PRED(graph, dist, pred):
    u, v, c_uv = graph.last_edge_updated

    if c_uv >= dist[u, v]:
        return dist, pred

    affected_sources = deque()
    affected_targets = deque()

    for k in graph.nodes:
        if (c_uv + dist[v, k]) < dist[u, k]:
            affected_targets.append(k)
        if (dist[k, u] + c_uv) < dist[k, v]:
            affected_sources.append(k)

    for j in affected_targets:
        for i in affected_sources:
            sum = dist[i, u] + c_uv + dist[v, j]
            if sum < dist[i, j]:
                dist[i, j] = sum
                pred[i, j] = u

    return dist, pred

Función Test

Una función para comprobar que la matriz de distancia y la matriz de predecesores coinciden:

"""
Comprueba si la matriz de distancia y la de predecesores, coinciden
"""
@staticmethod
def testDistPred(dist, pred):

    for node_source in range(len(dist)):
        for node_target in range(len(dist)):
            if node_source == node_target:
                continue

            pred_list = pred[node_source]
            distance_must = dist[node_source, node_target]
            target = node_target

            if distance_must == np.inf:
                if pred_list[target] == -1:
                    continue
                else:
                    print(f'({node_source}, {node_target}) must be -1')
                    return False

            distance = 0
            while True:
                predecesor = pred_list[target]
                source = predecesor

                if predecesor != -1:
                    distance += dist[predecesor, target]

                if source == -1:
                    if distance_must != distance:
                        print(f'({node_source}, {node_target}) not distance coincidence')
                        return False
                    break
                target = source

    return True

 

Script de prueba

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_prev.dijkstra_prev import *
from algorithms_prev.forest_pred import *
from algorithms_prev.abm_pred import *

#Grafos Aleatorios
graph = Graph.creategraph(6, .8)
graph.print_r()

dist, prev = Dijkstra_apsp_PREV(graph)
print(prev)

#graph.dynamic_incremental_edge(source=3, target=4, weight=2)
graph.insert_worst_edge()

print("------------------FOREST-----------------------")
dist2, prev2 = Forest_apsp_PRED(graph, dist.copy(), prev.copy())
print(prev2)
print("Data is correct? ", Graph.testDistPred(dist2, prev2))

print("----------------------ABM-------------------")
dist3, prev3 = ABM_Update_PRED(graph, dist.copy(), prev.copy())
print(prev3)
print("Data is correct? ", Graph.testDistPred(dist3, prev3))

Unit Test

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_prev.dijkstra_prev import *
from algorithms_prev.forest_pred import *
from algorithms_prev.abm_pred import *

graph = Graph.creategraph(20, .8)
dist_before, prev_before = Dijkstra_apsp_PREV(graph)
graph.insert_worst_edge()

def test_predecesors():
    dist, pred = Forest_apsp_PRED(graph, dist_before.copy(), prev_before.copy())
    np.testing.assert_equal(True, Graph.testDistPred(dist, pred))

    dist2, pred2 = ABM_Update_PRED(graph, dist_before.copy(), prev_before.copy())
    np.testing.assert_equal(True, Graph.testDistPred(dist2, pred2))

    #np.testing.assert_array_equal(pred_dijkstra, pred_fw)