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