# Synopse

This function implements Kuskal's algorithm for finding a graph Minimum Spanning Tree (MST).

• MST = iamstk_rob(graph)

• Output

• MST: Weighted Adjacency matrix representing the MST of the graph. 'Inf' value means unconnected vertices.
• Input

• graph: Weighted Adjacency matrix of the graph. 'Inf' value means unconnected vertices.

# Description

This function implements Kuskal's algorithm for finding a graph Minimum Spanning Tree (MST). It sorts the graph edges by weight and adds the smaller weights edges until it finds the MST, it also checks for cycles formation.

# Function Code

1 from numpy import*
2 def iamstk_rob(graph):
3    S = iamatrix2list(graph)
4    S = sorted(S,key=lambda S:S[2],reverse=True)
5    F = range(0,graph.shape[0])
6
7    for i in F:
8       F[i] = [i]
9    number_edges_MST = 0
10    number_edges_graph = graph.shape[0]
11    MST = ones((number_edges_graph,number_edges_graph))*float('inf')
12
13    while (S and number_edges_MST<(number_edges_graph-1)):
14       temp = S.pop()
15
16       for i in range(0,len(F)):
17          if(temp[0] in F[i]):
18             index1 = i
19          if(temp[1] in F[i]):
20             index2 = i
21
22
23       if(index1!=index2):
24          MST[temp[0],temp[1]] = MST[temp[1],temp[0]] = temp[2]
25
26
27          F[index1].extend(F[index2]) # Combina as duas árvores em uma
28
29          F.pop(index2)
30
31          number_edges_MST+=1
32
33
34
35    return MST
36
37 def iamatrix2list(mat_):
38    mat = mat_.copy()
39    mat[tril(ones(shape(mat))).astype(bool)] = float('inf')
40    [r,c] = where(mat!=float('inf'))
41    lista = vstack((r,c,mat[r,c]))
42    return (lista.transpose()).tolist()

# Examples

These examples calculate the MST for a simple graph and compares its processing time for graphs with different numbers of edges.

## Example 1:

2 from iamstk_rob import*
3 from courseIA368Q1S2012.tia_libGraph import drawGraphvizGraphMST
4
5 #Criação de dois grafos que serão usados nos testes
6 graph = array([[ inf,  7.,  inf,  inf,  5.,  inf, inf],
7                [  7.,  Inf,  8.,  9.,  7.,  Inf, Inf],
8                [ inf,   8.,  inf,  inf,  5., inf,  inf],
9                [ inf,   9.,   inf,  inf,  15.,  6., inf],
10                [ 5.,   7.,   5.,   15.,  inf,  8., 9.],
11                [ inf,   inf,  inf,   6.,   8., inf, 11.],
12                [ inf,  inf,   inf, inf,   9.,  11., inf]])
13 MST = iamstk_rob(graph)
14 mmgraphviz(adj2Graph(graph), 'Test graph with 7 vertices')
15 mmgraphviz(adj2Graph(MST), 'MST of the Graph')

## Performance Test

These tests are imported from MST Performance Test. Example using four different graphs. The results and the processing time are diplayed in a Table.

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

Autor Funcao A simple   A: rand(6,6)   100 nodes, complete   100 nodes, 0.5   Grafo MST
Roberto iamstk_rob 0.222 ms 9.0 0.167 ms 21.0 18.374 ms 318.055294457 10.175 ms 624.679654926 0.205 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