Performance Measurements: Minimum Spanning Tree - MST (v2)

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

1 #import rod_lib_perftest3
2 import rod_lib

Functions to be tested

POS-PROCESSAMENTO

Permite realizar diversas operacoes no resultado da função testada. Como o resultado será mostrado na tabela, é importante que essas operações resultem sempre em um número escalar (caso contrário não caberá na matriz).

No caso da MST, pode-se utilizar 3 funcoes de pos-processamento com o objetivo de gerar os tres resultados necessários para validar as funções: custo total (soma dos pessos), numero de arestas e numero de componentes conexos.

Na definição de cada função de pos-processamento, duas variáveis estão disponíveis:
  • x: é a variável que serviu de entrada na função testada
  • y: é o valor de retorno da função testada
1 #Initialize an empty function list vector:
2 listF = []

iaprim

1 import iaOPF
2 
3 #iaprim
4 posproc_pesos = lambda x,y: sum(y[y!=float('inf')])/2
5 posproc_narcos = lambda x,y: ((y<inf)*1.0).sum()/2
6 listPP = [posproc_pesos, posproc_narcos]
7 #listPP = []
8 fnc = [ 'iaOPF', 'iaprim', lambda x: iaOPF.iaprim(x), listPP]
9 listF.append(fnc)

André Costa

 1 #Andre - Kruskal
 2 import and_lib_3
 3 #Pos-Processamentos
 4 pp_pesos = lambda x,y: (x[y.astype(bool)]).sum()/2
 5 pp_narcos = lambda x,y: y.sum()/2
 6 
 7 def adapter(L):
 8     return L[:,:2].astype(int64)
 9 
10 listPP = [pp_pesos, pp_narcos]
11 fnc = ['Andre', 'mstKruskal', lambda x: rod_lib.rdlist2adj(adapter(and_lib_3.mstKruskal(x<inf, x))), listPP ]
12 listF.append(fnc)
13 
14 #Andre - Boruvka
15 import and_lib_4
16 fnc = ['Andre', 'mstBoruvka', lambda x: rod_lib.rdlist2adj(adapter(and_lib_4.mstBoruvka(x<inf, x))), listPP]
17 listF.append(fnc)
18 
19 #Andre - Prim
20 import and_lib_5
21 fnc = ['Andre', 'mstPrim', lambda x: rod_lib.rdlist2adj(adapter(and_lib_5.mstPrim(x<inf, x))), listPP ]
22 listF.append(fnc)

Wesley Angelino

 1 #Kruskal
 2 import wes_lib as wes
 3 
 4 import and_lib_3
 5 #Pos-Processamentos
 6 pp_pesos = lambda x,y: (x[y]).sum()/2 #(x*y).sum()/2
 7 pp_narcos = lambda x,y: y.sum()/2
 8 
 9 listPP = [pp_pesos, pp_narcos]
10 fnc = ['Wesley', 'Kruskal', lambda x: wes.Kruskal1(x, 'int')<inf, listPP ]
11 listF.append(fnc)

Roberto Souza

1 #Kruskal
2 import rob_biblio2 as rob
3 
4 npesos = lambda x,y: sum(y[y!=float('inf')])/2
5 narcos = lambda x,y: sum(y!=float('inf'))/2
6 
7 listPP = [npesos, narcos]
8 fnc = ['Roberto','`rob_biblio2 Kruskal`', lambda x: rob.kruskal(x), listPP]
9 listF.append(fnc)
/usr/local/lib/python2.6/dist-packages/scikits/__init__.py:1: UserWarning: Module dateutil was already imported from /usr/local/lib/python2.6/dist-packages/matplotlib-1.1.0-py2.6-linux-x86_64.egg/dateutil/__init__.pyc, but /usr/lib/pymodules/python2.6 is being added to sys.path
  __import__('pkg_resources').declare_namespace(__name__)

Fernanda

 1 #Kruskal
 2 import fer_lib as fer
 3 
 4 #Pos-Processamentos
 5 pp_pesos = lambda x,y: (x[y]).sum()/2 #(y*x).sum()/2
 6 pp_narcos = lambda x,y: y.sum()/2
 7 
 8 listPP = [pp_pesos, pp_narcos]
 9 fnc = ['Fernanda', 'Kruskal', lambda x: fer.kruskal(x)<inf, listPP ]
10 listF.append(fnc)

Wendell

 1 import wen_lib as wen
 2 
 3 #Pos-Processamentos
 4 pp_pesos = lambda x,y: x.astype('float')[wen.list2Adj(y, x.astype('float').shape[0]) < inf].sum()/2.
 5 pp_arcos = lambda x,y: len(wen.mstK(x.astype(float)))
 6 
 7 listPP = [pp_pesos, pp_arcos]
 8 #listPP = [pp_arcos]
 9 fnc = ['Wendell', 'Kruskal', lambda x: wen.mstK(x.astype(float)), listPP]
10 listF.append(fnc)

Eric

 1 import eri_lib as eri
 2 
 3 #Pos-Processamentos
 4 pp_pesos = lambda x,y: y[1]
 5 pp_arcos = lambda x,y: len(where(y[0]<inf)[0])/2
 6 pp_cc = lambda x,y: len(eri.adj2ccList(y[0]))
 7 
 8 listPP = [pp_pesos, pp_arcos, pp_cc]
 9 
10 fnc = ['Eric', 'Kruskal', lambda x: eri.kruskalMST(x), listPP]
11 listF.append(fnc)

Tiago

 1 import tia_libGraph as tia
 2 
 3 #Pos-Processamentos
 4 pp_narcos = lambda x,y: len(nonzero(y)[0])
 5 pp_pesos = lambda x,y: y.sum()
 6 pp_compConexo = lambda x,y: tia.countGraphCC(y)
 7 
 8 listPP = [pp_pesos,pp_narcos,pp_compConexo]
 9 
10 fnc = ['Tiago', 'Kruskal', lambda x: tia.tiaMSTKruskal(x.astype(float)), listPP]
11 listF.append(fnc)

Francisco

 1 import fra_lib as fra
 2 
 3 #Pos-Processamentos
 4 pp_pesos = lambda x,y: y[0][0]
 5 pp_arcos = lambda x,y: y[0][1]
 6 pp_cc = lambda x,y: y[0][2]
 7 
 8 listPP = [pp_pesos, pp_arcos, pp_cc]
 9 
10 fnc = ['Francisco', 'Kruskal', lambda x: fra.WrpKruskal(x), listPP]
11 listF.append(fnc)

Giovani

 1 import gio_lib as gio
 2 
 3 #Pos-Processamentos
 4 #pp_narcos = lambda x,y: len(nonzero(y)[0])
 5 #pp_pesos = lambda x,y: y.sum()
 6 pp_compConexo = lambda x,y: gio.giCounterCC(y)
 7 
 8 listPP = [pp_pesos,pp_narcos,pp_compConexo]
 9 
10 fnc = ['Giovani', 'Boruvka(TESTE)', lambda x: gio.giMST(x), listPP]
11 listF.append(fnc)

Thiago José

1 #Kruskal
2 import thi_lib as thiLib
3 
4 pp_pesos = lambda x,y: sum(y[y!=float('inf')])/2
5 pp_narcos = lambda x,y: sum(y!=float('inf'))/2
6 
7 listPP = [pp_pesos , pp_narcos]
8 fnc = ['Thiago', 'Kruskal', lambda x: thiLib.edgeList2AdjMat(thiLib.kruskal(x),x.shape[0]), listPP]
9 listF.append(fnc)

List of test values

rob_biblio2

 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 =array(A,dtype = float)
 8 i = range(0,6)
 9 A[i,i] = float('inf')
10 A = maximum(A,A.transpose())
11 test_1 = ['A: rand(6,6)', A]
12 listT.append(test_1)
13 
14 #Grafo completo com 100 nós
15 temp = randGraph(100,1,'yes')
16 test_2 = ['100 nodes, complete', temp]
17 listT.append(test_2)
18 
19 
20 #Grafo intermediário com 100 nós
21 temp3 = randGraph(100,0.5,'yes')
22 test_3 = ['100 nodes, 0.5', temp3]
23 listT.append(test_3)
24 
25 
26 # Grafo que é uma MST
27 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],
28            [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],
29            [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]])
30 test_4 = ['Grafo MST',temp5]
31 listT.append(test_4)
32 print type(temp5[0,0])
33 
34 #Testes debug
35 debug_1 = randGraph(10,1,'yes')
36 teste_deb = ['10 nodes, complete', debug_1]
37 #listT.append(teste_deb)
<type 'numpy.float64'>

Running tests

Autor Funcao A: rand(6,6)       100 nodes, complete       100 nodes, 0.5       Grafo MST      
iaOPF iaprim 0.325 ms 14.0 5.0   7.507 ms 260.715019323 99.0   7.485 ms 753.36346615 99.0   0.571 ms 139.0 9.0  
Andre mstKruskal 0.176 ms 14.0 5.0   2.651 ms 260.715019323 99.0   2.442 ms 753.36346615 99.0   0.234 ms 139.0 9.0  
Andre mstBoruvka 0.344 ms 14.0 5.0   11.192 ms 260.715019323 99.0   9.372 ms 753.36346615 99.0   0.643 ms 139.0 9.0  
Andre mstPrim 0.389 ms 14.0 5.0   65.762 ms 260.715019323 99.0   46.467 ms 753.36346615 99.0   0.645 ms 139.0 9.0  
Wesley Kruskal 0.446 ms 14.0 5   256.608 ms 260.715019323 99   316.464 ms 753.36346615 99   0.878 ms 139.0 9  
Roberto Kruskal 0.207 ms 14.0 5   37.019 ms 260.715019323 99   38.102 ms 753.36346615 99   0.341 ms 139.0 9  
Fernanda Kruskal 0.216 ms inf 5   40.215 ms inf 99   36.962 ms inf 99   0.323 ms inf 9  
Wendell Kruskal 0.124 ms inf 5   15.345 ms inf 99   8.265 ms inf 99   ERRO EXEC      
Eric Kruskal 0.158 ms 14.0 5 1 16.136 ms 260.715019323 99 1 8.669 ms 753.36346615 99 1 0.192 ms 139.0 9 1
Tiago Kruskal 0.326 ms 14.0 5 1 71.023 ms 260.715019323 99 1 60.027 ms 753.36346615 99 1 0.418 ms 139.0 9 1
Francisco Kruskal ERRO EXEC       ERRO EXEC       ERRO EXEC       ERRO EXEC      
Giovani Boruvka(TESTE) 1.306 ms inf 36 1 549.142 ms inf 10000 1 188.15 ms inf 10000 1 0.292 ms inf 100 1
Thiago Kruskal 0.222 ms 17.0 5   24.927 ms 4135.28593346 99   24.203 ms nan 83   0.405 ms 61.0 5