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)
Comentarios