# Function iamstk_wes()

## Synopse

iamstk_wes()

• mst = iamstk_wes(A)
• mst: Numpy array (A Matrix of adjacency with MST).
• A: Numpy array. Matrix of adjacency that will be checked.
• Call of the function: iamstk_wes(A)

### Description

iamstk_wes: Minimum spanning tree of a graph.

# Pseudocode

• Function iamstk_wes

Algoritmo 1:

# Function Code

``` 1 from numpy import *
2
3
4 def GrafoLA2MANew(L, grafo=False):
5     #pegando o número máximo da lista de arcos, correspondente a quantidade total de nós
6     L.sort(key=lambda x:x[1],reverse=True)
7     (a,n,c)=L[0]
8     n+=1
9     # criando uma matriz a com valores "inf"
10     A = ones((n,n)) * float('inf')
11     # preenchendo a matriz a onde tem como linha e coluna correspondente a matriz de arestas
12     while L:
13       Aux=L.pop()
14       A[Aux[0],Aux[1]]=Aux[2]
15       if grafo:
16         A[Aux[1],Aux[0]]=Aux[2]
17     return A
18
19 def iamstk_wes(A,NumType='float'):
20
21     from numpy import argsort, arange, array, triu
22
23     if NumType=='int':
24        A=array(A,float)
25
26     n = A.shape[0]
27     A1 = ones((n,n)) * 1
28     A1 = tril(A1)*1
29     A1[where(A1[:,:]!=0)]=float('inf')
30     A = triu(A)
31     A = A+A1
32     A[where(isnan(A))]=float('inf')
33
34     orig, dest = where(A[:,:]!=float('inf'))
35     weights = A[orig,dest]
36     edgeSeq = argsort(weights)
37     labels = arange(n)
38     n -= 1
39     T = []
40     for i in edgeSeq:
41         u,v = (orig[i],dest[i])
42         if not labels[u]==labels[v]:
43             T.append([u,v,weights[i]])
44             labels[labels==labels[v]] = labels[u]
45             if len(T)==n:
46                 Z = GrafoLA2MANew(T,False)
47                 return Z
```

# Example 1

``` 1 from iamstk_wes import iamstk_wes
2
3
4 a = array([[Inf,1.,1.,0.,8.],
5            [1.,Inf,2.,5.,7.],
6            [1.,2.,Inf,6.,9.],
7            [0.,5.,6.,Inf,10.],
8            [8.,7.,9.,10.,Inf]])
9
10 MK = iamstk_wes(a)
11 print MK
```
```[[ Inf   1.   1.   0.  Inf]
[ Inf  Inf  Inf  Inf   7.]
[ Inf  Inf  Inf  Inf  Inf]
[ Inf  Inf  Inf  Inf  Inf]
[ Inf  Inf  Inf  Inf  Inf]]
```

## Test:

Test using four different graphs. The results and the processing time are diplayed in a Table.

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

Autor Funcao A simple   A: rand(6,6)   100 nodes, complete   100 nodes, 0.5   Grafo MST
Wesley iamstk_wes 0.375 ms 9.0 0.239 ms 21.0 3.864 ms 318.055294457 3.569 ms 624.679654926 0.296 ms 139.0

### References

 [Feof2009] Paulo Feofiloff. Algoritmos para Grafos em C via Sedgewick. IME-USP. http://www.ime.usp.br/~pf/algoritmos_para_grafos

### Contributions

• Wesley Souza, 1o semestre de 2012.