Function iamstk_tia

Synopse

Input:
  • M: Array Adj. matrix
Output:
  • MST: Array: Adj matrix with the MST

Description

MST Kruskal based algorithm

Algorithm

Algoritmo 1:

Function Code

 1 from numpy import *
 2 from courseIA368Q1S2012.tia_libGraph import *
 3 
 4 '''
 5 ' Implementação do algoritmo Kruskal
 6 ' ***********
 7 ' Alteração 20/04 (otimizando o algoritmo)
 8 ' ***********
 9 ' @param matrix matriz de adjacência do grafo
10 ' @param allSubtrees sub árvores
11 ' @return MST
12 '''
13 def iamstk_tia(M):
14     n = len(M)
15 
16     #Copiando a matriz de entrada para usar na funcao
17     matrixCopy = triu(copy(M))
18 
19     #Tratando casos com Inf
20     matrixCopy[matrixCopy==Inf]=0
21     matrixCopy = nan_to_num(matrixCopy)
22 
23     edges = WeigthMA2Larcos(matrixCopy+transpose(matrixCopy))
24 
25     #Criando uma matriz de adjacência com 0's
26     MST = zeros((n,n))
27 
28     #Buscando os pesos do grafo de entrada
29     #weights = list(sort(matrixCopy[nonzero(matrixCopy)]))
30     edges = sorted(edges, key=lambda edges:edges[2])
31     #Criando as subarvores com apenas 1 elemento
32     #subtrees =[array([i]) for i in range(n)]
33     subtrees =[[i] for i in range(n)]
34 
35     #Condição de término (Faça enquanto tiver mais de uma subarvore)
36     while(len(subtrees)>1):
37 
38         #Buscando a aresta com o menor peso
39         currentEdge = edges.pop(0)
40         #Buscando os nós deste vértice
41         #x = where(matrixCopy[:,:]==currentEdge)[0][0]
42         #y = where(matrixCopy[:,:]==currentEdge)[1][0]
43         x = currentEdge[0]
44         y = currentEdge[1]
45 
46         #Buscando em quais subarvores estes nós estão
47         indexFirstSubtree = findSubtrees(subtrees,x)
48         indexSecondSubtree = findSubtrees(subtrees,y)
49 
50 
51         #Se os nós desta aresta estiverem em sub-árvores diferentes, adicione na MST
52         if(indexFirstSubtree!=indexSecondSubtree):
53             #Adicionando o vertice na matriz
54 
55             MST[x,y] = currentEdge[2]
56 
57             #Juntando 2 subarvores
58             #subtrees[indexFirstSubtree] = concatenate((subtrees[indexFirstSubtree],subtrees[indexSecondSubtree]))
59             subtrees[indexFirstSubtree].extend(subtrees[indexSecondSubtree])
60             subtrees.pop(indexSecondSubtree)
61 
62         #Removendo a aresta da fila
63         #weights = delete(weights,0)
64 
65         #Removendo aresta no grafo
66         matrixCopy[x,y] = 0
67 
68 
69     return MST

Algorithm

Performance Tests

Function is tested by running the tests defined at the page Connected Components Performance Test. The following code represent the steps to run these tests and show the results. Additionally, these information will also be summarized at the above page.

1. The module where the tests were subscribed must be imported. It's very important to run the SETUP(xsPackage, xsModule) function before executing the tests, as shown below:

Note: here you must choose between import BINARY or INFINITY WEIGHTED test module, according to the expected input of your function.

 1 from iamcc_test import objTestes_inf
 2 from iamstk_tia import iamstk_tia
 3 
 4 
 5 objTestes_inf.setup(xsPackage, xsModule)
 6 
 7 listF = []
 8 
 9 listPP = []
10 posproc_1 = lambda x,y: y[y!=Inf].sum()
11 listPP.append(posproc_1)
12 
13 fnc_1 = ['Tiago', 'iamstk_tia', lambda x:iamstk_tia(x), listPP]
14 listF.append(fnc_1)
<type 'numpy.float64'>

2. To finalize, run the tests using the imported test module object. Note: do not forget to configure the option output_format: rest, otherwise you will not visualize the results table.

1 objTestes_inf.runTests(listF)

gravando arquivo: /home/rubens/www/media/Attachments/iaOPF/iamstk_tia/testperf.pkl

Autor Funcao A simple   A: rand(6,6)   100 nodes, complete   100 nodes, 0.5   Grafo MST  
Tiago iamstk_tia 0.44 ms 14.0 0.374 ms 21.0 93.812 ms 318.055294457 60.673 ms 624.679654926 0.443 ms 139.0
Autor:tiagofrepereira
Data:04/07/2012