Function iamstk_rob

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:

 1 from courseIA368Q1S2012.wen_lib import adj2Graph
 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')
/media/_xsb/iaOPF/iamstk_rob/GRVIZ83483_001.png

Test graph with 7 vertices

/media/_xsb/iaOPF/iamstk_rob/GRVIZ83483_002.png

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

See also

  • iaprim - Prim's algorithm implementatoion for finding MSTs

Contributions

  • Roberto Souza, 1o semestre de 2012.