Performance Measurements: Dijkstra Algorithm (under development)

The following example uses this Performance Test function v3. In that link you can find more infirmation about how to use this function.

1 #import rod_lib_perftest3
2 import rod_lib

Functions to be tested

Post-processing

Allows you to perform diverse operations with the result of the function being tested. These results will be displayed in a table, so it is important that thoses operations performed result in a scalar value (otherwise the result won't fit the matrix).

You have available 2 variables two develop your post-processing routines:

  • x: is the input graph;
  • y: is the output vector.
1 #Initialize an empty function list vector:
2 listF = []

Roberto Souza

1 #Dijkstra
2 import rob_biblio2 as rob
3 
4 soma_pesos = lambda x,y: sum(y)
5 
6 listPP = [soma_pesos]
7 
8 fnc = ['Roberto','`rob_biblio2 Dijkstra`', lambda x: rob.dijkstra(x,0), listPP]
9 listF.append(fnc)

Eric

1 #Dijkstra
2 import eri_lib as eri
3 
4 soma_pesos = lambda x,y: sum(y)
5 
6 listPP = [soma_pesos]
7 fnc = ['`eri_7 Eric`','`eri_lib dijkstraMax()`', lambda x: eri.dijkstraMax(x,0), listPP]
8 listF.append(fnc)

Rodrigo

1 import rod_7
2 
3 pp_soma = lambda x,y: sum(y)
4 listPP = [pp_soma]
5 fnc = ['`rod_7 Rodrigo`', 'rddij', lambda x: rod_7.rddij(x,0), listPP]
6 listF.append(fnc)

Wesley

1 import wes_lib
2 
3 pp_soma = lambda x,y: sum(y)
4 listPP = [pp_soma]
5 fnc = ['Wesley', '`wes_7 Dijkstra1`', lambda x: wes_lib.Dijkstra1(x), listPP]
6 listF.append(fnc)

Wendell

1 import wen_lib as wen
2 
3 pp_soma = lambda x,y: sum(y)
4 listPP = [pp_soma]
5 fnc = ['Wendell', '`wen_7 Dijkstra`', lambda x: wen.djkMaxAdj(0, x), listPP]
6 listF.append(fnc)

Francisco

1 import fra_lib_7 as fra
2 
3 pp_soma = lambda x,y: y[2]
4 listPP = [pp_soma]
5 fnc = ['Francisco', '`fra_7 Dijkstra`', lambda x: fra.dijkstra(x, x.shape[0]-1,0), listPP]
6 listF.append(fnc)

Fernanda

1 import fer_lib as fer
2 
3 pp_soma = lambda x,y: sum(y)
4 listPP = [pp_soma]
5 fnc = ['Fernanda', '`fer_7 Dijkstra`', lambda x: fer.dijkstra(x,0), listPP]
6 listF.append(fnc)

Tiago

1 import tia_libGraph as tia
2 
3 pp_soma = lambda x,y: sum(y)
4 listPP = [pp_soma]
5 fnc = ['Tiago', '`tia_7 Dijkstra`', lambda x: tia.tiaDijkstra(x,0), listPP]
6 listF.append(fnc)

Heinz

1 import hei_libDijkstra as hei
2 
3 pp_soma = lambda x,y: sum(y)
4 listPP = [pp_soma]
5 fnc = ['Heinz', '`hei_7 DijkstraMax`', lambda x: hei.DijkstraMax(x,0), listPP]
6 listF.append(fnc)

Thiago José

1 import thi_lib
2 import numpy as np
3 
4 pp_soma = lambda x,y: sum(np.take(y, [0], 1))
5 listPP = [pp_soma]
6 fnc = ['Thiago', '`thi_7 Dijkstra (Max)`', lambda x: thi_lib.dijkstra(x,0,'max',False), listPP]
7 listF.append(fnc)

André

 1 import and_lib as an
 2 import numpy as np
 3 
 4 pp_soma = lambda x,y: sum(y[2])
 5 listPP = [pp_soma]
 6 
 7 def and_call(G):
 8     A = G!=float('inf')
 9     W = G.copy()
10     W[G==float('inf')] = 0
11     return an.opf(A,W, np.array([0]), costFunction=an.maxCost)
12 
13 fnc = ['Andre', '`and_7 OPF()`', lambda x: and_call(x), listPP]
14 listF.append(fnc)

List of test values

 1 from wen_lib import adj2Graph
 2 import rob_biblio2 as rob
 3 
 4 #Test Graph seen in class
 5 graph01 = array([[inf,3,inf,7,inf,inf,inf,inf,inf],[3,inf,2,inf,1,inf,inf,inf,inf],
 6 [inf,2,inf,inf,inf,11,inf,inf,inf],[7,inf,inf,inf,9,inf,5,inf,inf],
 7 [inf,1,inf,9,inf,4,inf,12,inf],[inf,inf,11,inf,4,inf,inf,inf,10],
 8 [inf,inf,inf,5,inf,inf,inf,2,inf],[inf,inf,inf,inf,12,inf,2,inf,6],[inf,inf,inf,inf,inf,10,inf,6,inf]])
 9 i = 0
10 
11 mmgraphviz(adj2Graph(graph01),'Test Graph seen in class')
12 
13 #Grafo de teste completo com 50 arestas
14 graph02 = rob.randGraph(50,1,'yes')
15 
16 #Grafo de teste completo com 100 arestas
17 graph03 = rob.randGraph(100,1,'yes')
18 
19 
20 #Initialize an empty test list vector:
21 listT = []
22 test_1 = ['Simple Test Graph', graph01]
23 listT.append(test_1)
24 
25 test_2 = ['Complete(v =50)', graph02]
26 listT.append(test_2)
27 
28 test_3 = ['Complete(v =100)', graph03]
29 listT.append(test_3)
30 
31 graph04 = array([[inf,3,inf,7,inf,inf,inf,inf,inf,inf,inf],[3,inf,2,inf,1,inf,inf,inf,inf,inf,inf],
32 [inf,2,inf,inf,inf,11,inf,inf,inf,inf,inf],[7,inf,inf,inf,9,inf,5,inf,inf,inf,inf],
33 [inf,1,inf,9,inf,4,inf,12,inf,inf,inf],[inf,inf,11,inf,4,inf,inf,inf,10,inf,inf],
34 [inf,inf,inf,5,inf,inf,inf,2,inf,inf,inf],[inf,inf,inf,inf,12,inf,2,inf,6,inf,inf],[inf,inf,inf,inf,inf,10,inf,6,inf,inf,inf],
35 [inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf],[inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf]])
36 mmgraphviz(adj2Graph(graph04),'Graph with 3 connected components')
37 test_4 = ['3 connected components', graph04]
38 listT.append(test_4)
/media/_xsb/courseIA368Q1S2012/comp_dijkstra/GRVIZ53958_001.png

Test Graph seen in class

/media/_xsb/courseIA368Q1S2012/comp_dijkstra/GRVIZ53958_002.png

Graph with 3 connected components

Running tests

Autor Funcao Simple Test Graph   Complete(v =50)   Complete(v =100)   3 connected components  
Roberto Dijkstra 0.479 ms 41.0 38.702 ms 453.871436882 272.046 ms 612.133723372 0.518 ms inf
Eric dijkstraMax() 0.622 ms 41.0 4.266 ms 453.871436882 10.405 ms 612.133723372 0.73 ms inf
Rodrigo rddij 0.268 ms 41.0 1.58 ms 453.871436882 3.321 ms 612.133723372 0.321 ms inf
Wesley Dijkstra1 0.391 ms 41.0 9.392 ms 453.871436882 31.669 ms 612.133723372 0.491 ms inf
Wendell Dijkstra 0.332 ms 41.0 35.828 ms 453.871436882 262.122 ms 612.133723372 0.367 ms inf
Francisco Dijkstra 0.267 ms 41.0 5.388 ms 453.871436882 19.309 ms 612.133723372 0.388 ms inf
Fernanda Dijkstra 0.487 ms 41.0 2.7 ms 453.871436882 5.568 ms 612.133723372 0.481 ms inf
Tiago Dijkstra 0.697 ms 41.0 13.192 ms 453.871436882 47.177 ms 612.133723372 0.726 ms inf
Heinz DijkstraMax 5.534 ms 41.0 1190.84 ms 490.476822644 11802.737 ms 614.593538698 ERRO EXEC  
Thiago Dijkstra (Max) 0.361 ms 41.0 34.534 ms 453.871436882 253.343 ms 612.133723372 ERRO EXEC  
Andre OPF() 1.214 ms 41.0 5.46 ms 453.871436882 13.926 ms 612.133723372 ERRO EXEC