Ya había trabajado anteriormente con los algoritmos de Dijkstra y Floyd-Warshall. En esta entrada se implementaron los algoritmos en Matlab. Esta vez usaremos Python 3.5 con la librería Numpy y el módulo de grafos dinámicos realizado anteriormente en esta entrada.
Dijkstra
El algoritmo de dijkstra es SSSP (Single Source Shortest Path), dado un nodo origen encontrar el camino más corto para todos los demás nodos. La función en el módulo es:
def sssp_dijkstra(self, source):
total_vertex = len(self.vertex)
Q = np.array(self.vertex)
dist = np.zeros(total_vertex)
dist.fill(np.inf)
dist[self.vertex == source] = 0
while len(Q) != 0:
min = np.inf
u = 0
for q in Q:
if dist[self.vertex == q] <= min:
min = dist[self.vertex == q]
u = q
Q = np.delete(Q, np.argwhere(Q == u))
for v in self.target[self.source == u]:
alt = dist[self.vertex == u] + self.get_weight(u, v)
index_v = self.vertex == v
if alt < dist[index_v]:
dist[index_v] = alt
Pero para adaptarla para todos los nodos, es decir para el problema APSP (All Pairs Shortest Path), solomente hacemos un llamado a la función anterior para cada nodo del grafo, el algoritmo:
def apsp_dijkstra(self):
result = np.full((self.vertex.size, self.vertex.size), np.inf)
count = 0
for v in self.vertex:
result[count] = self.sssp_dijkstra(v)
count = count + 1
return result
Con esto podemos tener una matriz de distancias, probemos los algoritmos con el siguiente script:
from _graph.GraphPro import GraphPro as g
from time import time
import os
os.system('clear')
print("<--------Test Dijkstra------->\n")
weights = [1, 2, 3, 4, 5]
graph = g.creategraph(6, .75, weights, directed=False)
graph.print_r()
print('.........................')
t = time()
print(graph.apsp_dijkstra())
elapsed = time() - t
print("Time: ", elapsed)
graph.draw()
El script anterior genera un grafo aleatorio con seis nodos, con una probabilidad de armar arco de 75%, unos pesos específicos y no dirigidos. Guardamos el tiempo de resolución del algoritmo Dijkstra y dibujamos el grafo.
Figura 1. Grafo generado aleatoriamente para el algoritmo Dijkstra
El resultado de los caminos más cortos, se presenta por consola:
<--------Test Dijkstra-------> Source: [ 0. 1. 0. 2. 0. 3. 0. 5. 1. 2. 1. 3. 1. 4. 1. 5. 2. 3. 2. 4. 3. 4. 3. 5. 4. 5.] Target: [ 1. 0. 2. 0. 3. 0. 5. 0. 2. 1. 3. 1. 4. 1. 5. 1. 3. 2. 4. 2. 4. 3. 5. 3. 5. 4.] Weight: [ 2. 2. 2. 2. 4. 4. 1. 1. 3. 3. 2. 2. 4. 4. 4. 4. 2. 2. 1. 1. 3. 3. 5. 5. 1. 1.] Vertex: [ 0. 1. 2. 3. 4. 5.] ......................... [[ 0. 2. 2. 4. 2. 1.] [ 2. 0. 3. 2. 4. 3.] [ 2. 3. 0. 2. 1. 2.] [ 4. 2. 2. 0. 3. 4.] [ 2. 4. 1. 3. 0. 1.] [ 1. 3. 2. 4. 1. 0.]] Time: 0.006327390670776367
El resultado del algoritmo se lee colocando los vértices de izquierda a derecha y de abajo hacia arriba. Por ejemplo para el camino más corto en el grafo de la Figura 1 del nodo 2 al nodo 5 es de 2.0.
Floyd-Warshall
Para el algoritmo de Floyd-Warshall tenemos:
def floyd_warshall(self):
total_vertex = len(self.vertex)
dist = np.zeros((total_vertex, total_vertex))
dist.fill(np.inf)
for idx in range(self.source.size):
index_s = self.vertex == self.source[idx]
index_t = self.vertex == self.target[idx]
dist[index_s, index_t] = self.weight[idx]
for index in range(self.vertex.size):
dist[index, index] = 0
for i in range(self.vertex.size):
for j in range(self.vertex.size):
for k in range(self.vertex.size):
if dist[i, j] > dist[i, k] + dist[k, j]:
dist[i, j] = dist[i, k] + dist[k, j]
return dist
Para este caso pasamos el mismo grafo para comprobar que sea la misma respuesta, editamos nuestro script de prueba:
from _graph.GraphPro import GraphPro as g
from time import time
import os
os.system('clear')
print("<--------Test Dijkstra------->\n")
weights = [1, 2, 3, 4, 5]
#graph = g.creategraph(6, .75, weights, directed=False)
sources = [0, 1, 0, 2, 0, 3, 0, 5, 1, 2, 1, 3, 1, 4, 1, 5, 2, 3, 2, 4, 3, 4, 3, 5, 4, 5]
targets = [1, 0, 2, 0, 3, 0, 5, 0, 2, 1, 3, 1, 4, 1, 5, 1, 3, 2, 4, 2, 4, 3, 5, 3, 5, 4]
weights = [2, 2, 2, 2, 4, 4, 1, 1, 3, 3, 2, 2, 4, 4, 4, 4, 2, 2, 1, 1, 3, 3, 5, 5, 1, 1]
graph = g(sources, targets, weights)
graph.print_r()
print('.........................')
t = time()
print(graph.floyd_warshall())
elapsed = time() - t
print("Time: ", elapsed)
graph.draw()
Los resultados fueron idénticos:
<--------Test Floyd-Warshall-------> Source: [0 1 0 2 0 3 0 5 1 2 1 3 1 4 1 5 2 3 2 4 3 4 3 5 4 5] Target: [1 0 2 0 3 0 5 0 2 1 3 1 4 1 5 1 3 2 4 2 4 3 5 3 5 4] Weight: [2 2 2 2 4 4 1 1 3 3 2 2 4 4 4 4 2 2 1 1 3 3 5 5 1 1] Vertex: [0 1 2 3 4 5] ......................... [[ 0. 2. 2. 4. 2. 1.] [ 2. 0. 3. 2. 4. 3.] [ 2. 3. 0. 2. 1. 2.] [ 4. 2. 2. 0. 3. 4.] [ 2. 4. 1. 3. 0. 1.] [ 1. 3. 2. 4. 1. 0.]] Time: 0.0016369819641113281
Bueno, no tan idénticos. El Floyd-Warshall duró significativamente menos. Aunque en el anterior entrada de Matlab se notaba que el algoritmo de Dijkstra se demoraba mucho más. También debemos de probarlo en Python 3.5
Comparación de algoritmos
Para la comparación de los algoritmos se implementa una clase para pruebas
from _graph.GraphPro import GraphPro as g
from time import time
import numpy as np
class GraphTest:
def __init__(self, from_num_nodes=5, until_num_nodes=20, probability_edges=.5, num_tries=3000, weights=[1, 2, 3, 4, 5, 6]):
self.from_num_nodes = from_num_nodes
self.until_num_nodes = until_num_nodes
self.probability_edges = probability_edges
self.num_tries = num_tries
self.weights = weights
def mean(self, num_nodes):
mean_dijkstra = 0
mean_floyd = 0
if self.num_tries <= 0:
return 0
for times in range(self.num_tries):
graph = g.creategraph(num_nodes, self.probability_edges, self.weights)
t = time()
graph.apsp_dijkstra()
lapsed = time() - t
mean_dijkstra = mean_dijkstra + lapsed
t = time()
graph.floyd_warshall()
lapsed = time() - t
mean_floyd = mean_floyd + lapsed
return [mean_dijkstra / self.num_tries, mean_floyd / self.num_tries]
def node_increments(self):
num_nodes = self.from_num_nodes
num_tries = self.until_num_nodes-self.from_num_nodes
results = np.zeros((2, num_tries))
for x in range(num_tries):
print('Size nodes: ', num_nodes)
times = self.mean(num_nodes)
results[0, x] = times[0]
results[1, x] = times[1]
num_nodes = num_nodes + 1
return results
Lo que realiza este script es muy similar al que realiza mi anterior entrada en Matlab. Genera miles de veces grafos aleatorios con cierta cantidad de nodos. Cuando se promedio el tiempo de resolución del algoritmo, se incrementa el número de nodos a generar y se analiza otra vez miles de veces y se promedia el tiempo.
La función mean( num_nodes ) es la que intenta varias veces con grafos aleatorios en cierta cantidad de nodos. Los algoritmos se ejecutan uno después del otro para que analizen el mismo grafo.
La función node_increments( ) es la que llama la función anterior mientras va incrementando el número de nodos. Los resultados se van almacenando y se retornan.
El siguiente script utiliza los métodos anteriores:
import matplotlib.pyplot as plt
from GraphTest import GraphTest
import numpy as np
import os
os.system('clear')
print("<--------Test ------->\n")
test = GraphTest(num_tries=1000)
results = test.node_increments()
num_nodes = np.arange(test.from_num_nodes, test.until_num_nodes, 1)
np.savetxt('test_algoritms_apsp.out', (num_nodes, results[0], results[1]))
plt.plot(num_nodes, results[0], 'ro', num_nodes, results[1], 'r--')
plt.ylabel('Tiempo en promedio para resolver')
plt.xlabel('Número de nodos')
plt.show()
Este script indica que intenté 1000 veces grafos aleatorios con un mismo número de nodos. Los resultados se almacenan en un archivo, por si el usuario desea analizar los resultados con otra herramienta. Los resultados se grafican con la función de matplotlib. La gráfica:
Figura 2. Comparación entre Dijkstra y Floyd-Warshall
La Figura 2 muestra una comparación entre los tiempos de resolución de APSP para varios grafos aleatorios con distintos números de nodos, desde 5 nodos hasta 20 nodos. El código fuente se encuentra en mi repositorio público: https://github.com/arturoverbel/graph_python.
Conclusiones
Así como en la entrada anterior, donde se realiza la comparación de Dijkstra y Floyd-Warshall en Matlab, Floyd-Warshall muestra un crecimiento menos pronunciado que Dijkstra.
1 Pingback