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.