Function imstk_fra

Francisco Leite | Página Inicial

Synopse

Brief function synopse: This function returns the Minimum Spanning Tree (MST) of a connected graph G.

  • array= imstk_fra(A)
    • Output
      • Array: MST A.
    • Input
      • A: Array. Adjacency matrix.

Description

Given an adjacency matrix A representing a connected graph G, the function returns the A´s MST, using kruskal algorithm. For each vertex v a list of visited vertex exists in order to check for cycles.

Note: G must be fully connected.

Function Code

 1 from numpy import *
 2 from iacc_fra import ianeighvert
 3 
 4 def iaL2adj(L):
 5    # matrix form W U V
 6    n = max([max(L[::,1]),max(L[::,2])])+1
 7    A = ones((n,n)) * float('inf')
 8    # symmetric matrix
 9    A[L[::,1],L[::,2]]=L[::,0]
10    A[L[::,2],L[::,1]]=L[::,0]
11    return A
12 
13 # transforms adjacency matrix into list with weights
14 def iaadj2listW(L):
15     vx=L.shape
16     v=vx[0]
17     ind=arange(v)
18     tam=0;
19     lista=[]
20     i=0
21     for r in ind:
22         lv=ianeighvert(L,r)
23         for nbv in lv:
24             if nbv>r:
25                 lista.append((L[r,nbv],int(r),int(nbv)))
26     return array(lista)
27 
28 
29 # Kruskal algorithm
30 def iamstk_fra(L):
31    n=L.shape[0]
32    b=ones((n,n),float)*float('inf')
33    d=diag(diag(b))
34    L=L+d
35    G=iaadj2listW(L)
36    edges=[]
37    edgen=0
38    for i in arange(G.shape[0]):
39      edges.append((float(G[i,0]),int(G[i,1]),int(G[i,2])))
40    Q = sorted (edges)
41    T = []
42    clusters = [[] for i in range(n)]
43    for i in arange(n):
44      clusters[i].append(i)
45    i = 0
46    T_weight = 0
47    while len (T) < n - 1:
48         w=Q[i][0]
49         u=Q[i][1]
50         v=Q[i][2]
51         if clusters[u] != clusters[v]:
52             T.append ((int(w),int(u),int(v)))
53             clusters[u].extend(clusters[v])
54             for l in clusters[v]:
55                clusters[l] = clusters[u]
56             T_weight += w
57             edgen+=1
58         i = i + 1
59 
60    return T_weight,T

Example

Example 1

Simple graph with 5 vertex

 1 from iamstk_fra import *
 2 from courseIA368Q1S2012.wen_lib import adj2Graph
 3 
 4 d=ones((5,5),int)
 5 d=d*float("inf")
 6 d[0,1]=1
 7 d[0,2]=1
 8 d[0,3]=1
 9 d[1,0]=1
10 d[1,4]=1
11 d[2,0]=1
12 d[2,4]=1
13 d[3,0]=1
14 d[3,4]=1
15 d[4,1]=1
16 d[4,2]=1
17 d[4,3]=1
18 graph=adj2Graph(d)
19 mmgraphviz(graph, 'Graph with 5 vertex')
20 r1=iamstk_fra(d)
21 print ("Sum:")
22 print (r1[0])
Sum:
4.0
/media/_xsb/iaOPF/iamstk_fra/GRVIZ56159_001.png

Graph with 5 vertex

Example 2

Greater 15 vertex graph

 1 import courseIA368Q1S2012.fra_lib as lib
 2 
 3 M=array([[7,0,1],[5,0,4],[1,0,3],[2,1,2],[1,2,4],[2,4,5],[9,5,11],[2,11,10],
 4 [1,10,12],[2,14,12],[1,14,13],[2,9,13],[1,9,8],[2,7,8],[1,7,6],[5,3,6],[1,2,8],
 5 [4,4,10],[8,5,9],[3,3,9],[4,3,4],[6,6,10]])
 6 f=iaL2adj(M)
 7 graph1=adj2Graph(f)
 8 mmgraphviz(graph1, 'Graph with 15 vertex')
 9 r1=iamstk_fra(f)
10 print ("Sum:")
11 print (r1[0])
12 a,b=lib.list2array(r1[1])
13 g=lib.L2adj(a,b)
14 mst=adj2Graph(g)
15 mmgraphviz(mst, 'MST Graph' )
Sum:
22.0
/media/_xsb/iaOPF/iamstk_fra/GRVIZ56159_002.png

Graph with 15 vertex

/media/_xsb/iaOPF/iamstk_fra/GRVIZ56159_003.png

MST Graph

Test:

Test using four different graphs. The results and the processing time are diplayed in a Table. See also MST performance test comparisson

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

Autor Funcao A simple   A: rand(6,6)   100 nodes, complete   100 nodes, 0.5   Grafo MST  
Francisco iamstk_fra 0.352 ms 9.0 0.36 ms 21.0 46.726 ms 318.055294457 22.973 ms 624.679654926 0.394 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
[Naha2011]Nahla Ibrahim. Optimal Spanning Trees. Stellenbosch University, South Africa

Algorithm

Algoritmo 1:

See also

A list of other related functions can be found on link below: