Después de realizar los algoritmos para grafos en Python y Matlab. Vamos a proceder a compararlos.

Pueden revisar los anteriores entradas de estos algoritmos en Algoritmos Dijkstra & Floyd-Warshall y Dijkstra & Floyd-Warshall – Python.

Para realizar una correcta comparación se realizó un programa en Matlab para generar grafos con cierto número de nodos, una probabilidad de conexión entre nodos y el nombre del archivo en el que se quiere exportar el grafo. Los pesos se establecen aleatoriamente entre el 1 y el 9:

function [] = exportGraph(nodes, probability, nameFile)
 numNodes = nodes;

 w = [1 2 3 4 5 6 7 8 9];
 G = randgraph(numNodes,probability, w);
 
 plot(G,'EdgeLabel',G.Edges.Weight);
 
 fileID = fopen(strcat('export/',nameFile,'.txt'),'w');

 list = table2array(G.Edges);
 total = numedges(G);
 
 for i = 1:total
 fprintf(fileID,'%d %d %d\n',list(i,1), list(i,2), list(i,3) );
 end
 
 fclose(fileID);

Ok. De aquí entonces podemos formar varios grafos usando en la consola de Matlab:

>> exportGraph(100, 0.45, 'cien')

En la línea anterior estamos diciendo que exporte un grafo con 100 nodos y que se conecten con una probabilidad de 0.45 y que el nombre del archivo sea cien, este comando generará un archivo en export/cien.txt con los datos. El archivo se verá como:

1 4 6
1 5 3
1 6 7
1 8 8
1 10 7
2 1 2
2 3 6
2 5 8
2 9 9
3 1 9
3 4 9
3 5 2
3 7 7
4 3 1
4 5 1
4 6 8
4 8 4
4 9 6
4 10 8
5 2 5
5 3 6
5 4 5
5 6 5
5 7 1
5 8 7
5 9 2
5 10 7
6 4 7
6 5 2
6 10 8
7 10 9
8 2 6
8 4 6
8 10 1
9 1 7
9 2 7
9 3 3
9 4 5
9 5 9
9 7 2
9 8 9
10 4 6
10 7 6

Esta es una lista de edges donde la primera y la segunda columna son nodos y la tercera columna es el peso del edge.

Además el programa pinta el grafo, aquí tenemos algunos generados:

Figura 1. Collección de grafos generados con la función exportGraph( ). Grafo A son 10 nodos, grafo B son cincuenta nodos y el grafo C tiene cien nodos.

Ahora que tenemos nuestro generador de grafos, veamos que tal se comparta nuestro programa en Matlab y Python para cargar el camino más corto de todos los pares en grafos de 500 nodos.

Para matlab se realizó el siguiente código:

clc

[s t w] = readFileWithWeight("export/trecientos.txt");
G = digraph(s,t,w);
%plot(G,'EdgeLabel',w)

tic;
%dist = floyd_warshall(G);
dist = dijkstra(G);
tiempo = toc

Solo baste con comentar y descomentar las lineas 8 y 9 para trabajar con Dijkstra o Floyd-Warshall. Ahora para Python se realizó el siguiente script:

import matplotlib.pyplot as plt
import networkx as nx
import graph as g
import time
import os

time1 = time.time()
os.system('cls')

f = open("export/quinientos.txt","r")

G = nx.Graph()

for line in f:
    s,d,w = line.split(' ')
    w = w.replace('\n', '')
    G.add_weighted_edges_from([(s,d,w)])

Gr = g.graph()
Gr.setGraph(G)

print("--- %s seconds load Graph ---" % (time.time() - time1))

timeO = time.time()
Gr.floyd_warshall()
print("--- %s seconds Distances ---" % (time.time() - time1))

Con este script cargamos el archivo y medimos el tiempo, tener en cuenta que utlizamos la misma clase de la entrada anterior que se encuentra en GitHub.

Ahora realizemos las comparaciones en una hoja de cálculo:

En la tabla anterior tenemos las columnas de Python y Matlab y en las filas los algoritmos divididos cada una en 2 filas que significa el tiempo en que se demoró cargando el archivo y el tiempo del algoritmo.

Podemos observar que para Dijkstra el tiempo es más rápido en Python que en Matlab. Por casi 200 segundos más pero para Floy-Warshall el tiempo en Python es mucha más lento que en Matlab. En Matlab solo duró 3 segundos en responder.

Se repetieron las pruebas con grafos del mismo tamaño y los tiempos de respuesta son muy parecidos.

Para el algoritmo de Dijkstra se utilizaran algunas técnicas, digamos que no es sencillo calcular la mínima distancia de todos los pares uno a uno con Dijkstra, por eso se demoran tanto en los 2 lenguajes, apesar de eso Python fue más rápido que Matlab.

Para el algoritmo de Floyd-Warshall el algoritmos es más sencillo y en realidad entre los dos algoritmos es muy parecido las sencentias pero en Python tardó un minuto y en Matlab tardó solo 3 segundos.