Performance Measurements: Minimum Spanning Tree - MST

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

1 import rod_lib_perftest2
2 import rod_lib

Functions to be tested

1 #Initialize an empty function list vector:
2 listF = []

iaprim

 1 import iaOPF
 2 
 3 #iaprim
 4 fnc = [lambda x: iaOPF.iaprim(x) < inf, 'iaprim', 'iaOPF']
 5 listF.append(fnc)
 6 
 7 #iaprim2
 8 fnc = [lambda x: iaOPF.iaprim2(x) < inf, 'iaprim2', 'iaOPF']
 9 listF.append(fnc)
10 
11 #iaprim3
12 fnc = [lambda x: iaOPF.iaprim3(x) < inf, 'iaprim3', 'iaOPF']
13 listF.append(fnc)

André Costa

 1 def adapter(L):
 2     return L[:,:2].astype(int64)
 3 
 4 #Andre - Kruskal
 5 import and_lib_3
 6 fnc = [lambda x: rod_lib.rdlist2adj(adapter(and_lib_3.mstKruskal(x<inf, x))) > 0, 'mstKruskal', 'Andre']
 7 listF.append(fnc)
 8 
 9 #Andre - Boruvka
10 import and_lib_4
11 fnc = [lambda x: rod_lib.rdlist2adj(adapter(and_lib_4.mstBoruvka(x<inf, x))) > 0, 'mstBoruvka', 'Andre']
12 listF.append(fnc)
13 
14 #Andre - Prim
15 import and_lib_5
16 fnc = [lambda x: rod_lib.rdlist2adj(adapter(and_lib_5.mstPrim(x<inf, x))) > 0, 'mstPrim', 'Andre']
17 listF.append(fnc)

Roberto Souza

1 #Kruskal
2 from rob_biblio2 import kruskal
3 fnc = [lambda x: kruskal(x) < inf, 'Kruskal', 'Roberto']
4 listF.append(fnc)

Heinz

1 #Boruvka
2 from hei_libBoruvka import mtrz_Boruvka_arr
3 fnc = [lambda x: mtrz_Boruvka_arr(x) > 0, 'Boruvka', 'Heinz']
4 listF.append(fnc)

Francisco

1 #Kruskal
2 import fra_lib as fra
3 fnc = [lambda x: fra.L2adj1(array(fra.frakruskal(x)[1])), 'Kruskal', 'Francisco']
4 listF.append(fnc)

Tiago

1 #Kruskal
2 import tia_libGraph as tia
3 fnc = [lambda x: tia.tiaMSTKruskal(x) > 0, 'Kruskal', 'Tiago']
4 listF.append(fnc)

Wesley

1 #Kruskal
2 import wes_lib as wes
3 fnc = [lambda x: wes.Kruskal1(x,'int')< inf, 'Kruskal', 'Wesley']
4 listF.append(fnc)

Eric

1 #Kruskal
2 import eri_lib
3 fnc = [lambda x: eri_lib.kruskalMST(x)[0] < inf, 'Kruskal', 'Eric']
4 listF.append(fnc)

Fernanda

1 #Kruskal
2 import fer_lib as fer
3 fnc = [lambda x: fer.kruskal(x)< inf, 'Kruskal', 'Fernanda']
4 listF.append(fnc)

Thiago

1 import thi_lib as thi
2 
3 #Kruskal
4 #fnc = [lambda x: thi.kruskal(x) < inf, 'Kruskal', 'Thiago']
5 fnc = [lambda x: thi.edgeList2AdjMat(thi.kruskal(x),x.shape[0]) < inf, 'Kruskal', 'Thiago']
6 listF.append(fnc)

List of test values

 1 from rob_biblio2 import randGraph
 2 
 3 #Initialize an empty test list vector:
 4 listT = []
 5 #Grafico aleatório 6x6
 6 A = random.random_integers(1,10,(6,6))
 7 A = maximum(A,A.transpose())
 8 B = iaOPF.iaprim(A)
 9 test_1 = ['A: rand(6,6)', A, B < inf]
10 listT.append(test_1)
11 
12 #Grafo completo com 100 nós
13 temp = randGraph(100,1,'yes')
14 temp2 = iaOPF.iaprim(temp)
15 test_2 = ['100 nodes, complete',temp,temp2<inf]
16 listT.append(test_2)
17 
18 #Grafo intermediário com 100 nós
19 temp3 = randGraph(100,0.5,'yes')
20 temp4 = iaOPF.iaprim(temp3)
21 test_3 = ['100 nodes, 0.5',temp3,temp4<inf]
22 listT.append(test_3)
23 
24 
25 # Grafo que é uma MST
26 temp5 = array([[inf,inf,10,inf,inf,inf,inf,inf,inf,inf],[inf,inf,13,11,inf,inf,inf,inf,inf,inf],[10, 13, inf, inf, 12, inf, inf, inf, inf, inf],[inf, 11,inf,inf,inf,inf,inf,15,inf,inf],
27            [inf, inf,12,inf,inf,inf,inf,inf,inf,inf],[inf,inf,inf,inf,inf,inf,inf,20,inf,inf],[inf,inf,inf,inf,inf,inf,inf,14,11,33],
28            [inf,inf,inf,15,inf,20,14,inf,inf,inf],[inf,inf,inf,inf,inf,inf,11,inf,inf,inf],[inf,inf,inf,inf,inf,inf,33,inf,inf,inf]])
29 temp6 = iaOPF.iaprim(temp5)
30 test_4 = ['Grafo MST',temp5,temp6<inf]
31 listT.append(test_4)

Running tests

Autor Funcao A: rand(6,6) 100 nodes, complete 100 nodes, 0.5 Grafo MST
iaOPF iaprim 0.335 ms (True) 7.468 ms (True) 7.466 ms (True) 0.581 ms (True)
iaOPF iaprim2 0.115 ms (True) 4.412 ms (True) 4.418 ms (True) 0.105 ms (True)
iaOPF iaprim3 0.191 ms (True) 5.114 ms (True) 5.145 ms (True) 0.241 ms (True)
Andre mstKruskal 0.196 ms (True) 2.563 ms (True) 2.468 ms (True) 0.237 ms (True)
Andre mstBoruvka 0.439 ms (True) 12.651 ms (True) 9.212 ms (True) 0.656 ms (True)
Andre mstPrim 0.409 ms (True) 65.917 ms (True) 46.812 ms (True) 0.669 ms (True)
Roberto Kruskal 0.306 ms (True) 63.253 ms (True) 71.442 ms (True) 0.438 ms (True)
Heinz Boruvka 3.081 ms (True) ERRO EXEC ERRO EXEC 5.602 ms (True)
Francisco Kruskal 0.392 ms (True) 32.976 ms (True) 31.87 ms (False) 0.68 ms (False)
Tiago Kruskal 2.038 ms (False) 183.856 ms (False) 243.507 ms (False) 1.599 ms (False)
Wesley Kruskal 0.773 ms (True) 183.367 ms (True) 330.388 ms (True) 0.901 ms (True)
Eric Kruskal 0.245 ms (True) 16.508 ms (True) 22.153 ms (False) 0.48 ms (False)
Fernanda Kruskal 0.309 ms (True) 53.216 ms (True) 49.447 ms (False) 0.606 ms (False)
Thiago Kruskal 0.202 ms (True) 15.096 ms (True) 9.054 ms (True) 0.215 ms (True)

Debbuging

 1 print "Grafo Teste:"
 2 print A
 3 print "\nMST (iaprim):"
 4 print B
 5 
 6 C = adapter(and_lib_3.mstKruskal(A<inf, A))
 7 D = and_lib_4.mstBoruvka(A<inf, A)
 8 C_1 = rod_lib.rdlist2adj(C)
 9 D_1 = rod_lib.rdlist2adj(D)
10 E_1 = fra.L2adj1(array(fra.frakruskal(A)[1]))
11 F_1 = tia.tiaMSTKruskal(A)
12 H   = mtrz_Boruvka_arr(A)
13 
14 
15 
16 print "\nmstKruskal: "
17 print C
18 print "\nmstBoruvka: "
19 print D
20 print "\nmstKruskal (matriz adjacencia):"
21 print C_1
22 print "\nmstBoruvka (matriz adjacencia):"
23 print D_1
24 print "\nmstfraKruskal: "
25 print E_1
26 print "\nmsttiaMSTKruskal: "
27 print F_1
28 
29 print "\mstHeinzBoruvka: "
30 print H
Grafo Teste:
[[ 5  9 10 10  9  3]
 [ 9  5  9  8  6 10]
 [10  9  1 10 10  8]
 [10  8 10  7  7  3]
 [ 9  6 10  7  5  6]
 [ 3 10  8  3  6  1]]

MST (iaprim):
[[ Inf  Inf  Inf  Inf  Inf   3.]
 [ Inf  Inf  Inf  Inf   6.  Inf]
 [ Inf  Inf  Inf  Inf  Inf   8.]
 [ Inf  Inf  Inf  Inf  Inf   3.]
 [ Inf   6.  Inf  Inf  Inf   6.]
 [  3.  Inf   8.   3.   6.  Inf]]

mstKruskal: 
[[3 5]
 [0 5]
 [1 4]
 [4 5]
 [2 5]]

mstBoruvka: 
[[0 5 3]
 [1 4 6]
 [2 5 8]
 [3 5 3]
 [4 5 6]]

mstKruskal (matriz adjacencia):
[[ 0.  0.  0.  0.  0.  1.]
 [ 0.  0.  0.  0.  1.  0.]
 [ 0.  0.  0.  0.  0.  1.]
 [ 0.  0.  0.  0.  0.  1.]
 [ 0.  1.  0.  0.  0.  1.]
 [ 1.  0.  1.  1.  1.  0.]]

mstBoruvka (matriz adjacencia):
[[ 0.  0.  0.  0.  0.  1.  0.  0.  0.]
 [ 0.  0.  0.  0.  1.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  1.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  1.  0.  0.  0.]
 [ 0.  1.  0.  0.  0.  1.  0.  0.  0.]
 [ 1.  0.  1.  1.  1.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]]

mstfraKruskal: 
[[ 0.  0.  0.  0.  0.  1.]
 [ 0.  0.  0.  0.  1.  0.]
 [ 0.  0.  0.  0.  0.  1.]
 [ 0.  0.  0.  0.  0.  1.]
 [ 0.  1.  0.  0.  0.  1.]
 [ 1.  0.  1.  1.  1.  0.]]

msttiaMSTKruskal: 
[[ 0.  0.  0.  0.  0.  3.]
 [ 0.  0.  0.  0.  6.  0.]
 [ 0.  0.  0.  0.  0.  8.]
 [ 0.  0.  0.  0.  0.  3.]
 [ 0.  0.  0.  0.  0.  6.]
 [ 0.  0.  0.  0.  0.  0.]]
\mstHeinzBoruvka: 
[[ 0.  0.  0.  0.  0.  3.]
 [ 0.  0.  0.  0.  6.  0.]
 [ 0.  0.  0.  0.  0.  8.]
 [ 0.  0.  0.  0.  0.  3.]
 [ 0.  6.  0.  0.  0.  6.]
 [ 3.  0.  8.  3.  6.  0.]]