Function iaprim

Description

Find the MST - Minimum Spanning Tree of a weighted graph represented by its weighted matrix.

Synopse

Create a weighted matrix MST of a graph represented by its weighted matrix.

  • edges = iaprim(A)
    • A: Input weighted matrix. Non connected nodes have weigh 'Inf'.
    • B: Output weighted matrix of MST of A.

Comments on the experiments:

iaprim is an optimized version of iaprim2, where the loops were removed. But, surprisely, iaprim takes longer to execute for graph with less than 2000 vertices. Also, if the matrix is too big, the results of iaprim and iaprim2 may differ. We need to investigate if this difference is due to ties on the values.

Loops optimized, same algorithms as iaprim2

 1 from numpy import *
 2 
 3 def iaprim(A, root=0):
 4 
 5   # prevents zero-weighted MSTs
 6   A = A.astype('double')
 7 
 8   n = A.shape[0]
 9   if n==0:
10     return []
11   d = zeros(n)
12   pred = zeros(n,int)
13   B = ones(A.shape)*float("inf")
14 
15   b0 = root         # first vertex as root
16   Q = range(0,n)    # all vertices
17   Q.remove(root)    # except the root
18   d[Q] = A[Q,b0]    # distances from root
19   pred[Q] = b0      # predecessor as root
20   while Q != []:
21     s = argmin(d[Q])
22     closest_i = Q[s] # find vertex in Q with smallest weight from b0
23     Q.remove(closest_i)
24     b0 = closest_i
25     b1 = pred[closest_i]
26     B[b0,b1] = B[b1,b0] = A[b0,b1] # insert this vertex in MST weight matrix
27     if Q == []:
28       break
29     QA=array(Q)
30     iii = where(A[QA,closest_i] < d[QA])
31     d[QA[iii]] = A[QA[iii],closest_i]     # update weights to pred
32     pred[QA[iii]] = closest_i             # update pred
33   return B

Optimization of finding minimum weight

 1 from numpy import *
 2 
 3 def iaprim3(A, root=0):
 4 
 5   n = A.shape[0]
 6   if n==0:
 7     return []
 8   d = zeros(n)
 9   pred = zeros(n,int)
10   B = ones(A.shape)*float("inf")
11 
12   b0 = root
13   Q = range(0,n)
14   Q.remove(root)
15   for i in Q:
16     d[i] = A[i,b0] # distance
17     pred[i] = b0      # predecessor
18 
19   while Q != []:
20     s = argmin(d[Q])
21     closest_i = Q[s] # find vertex in Q with smallest weight from b0
22     Q.remove(closest_i)
23     b0 = closest_i
24     b1 = pred[closest_i]
25     B[b0,b1] = B[b1,b0] = A[b0,b1]
26     for i in Q:
27         dd = A[i,closest_i]
28         if dd < d[i]:
29             d[i] = dd
30             pred[i] = closest_i
31 
32   return B

Simpler version

 1 from numpy import *
 2 
 3 def iaprim2(A, root=0):
 4 
 5   n = A.shape[0]
 6   if n==0:
 7     return []
 8   d = zeros(n)
 9   pred = zeros(n,int)
10   B = ones(A.shape)*float("inf")
11 
12   b0 = root
13   Q = range(0,n)
14   Q.remove(root)
15   for i in Q:
16     d[i] = A[i,b0] # distance
17     pred[i] = b0      # predecessor
18 
19   while Q != []:
20     min_d = 1e20
21     for i in Q:
22         if d[i] < min_d:
23             min_d = d[i]
24             closest_i = i
25     Q.remove(closest_i)
26     b0 = closest_i
27     b1 = pred[closest_i]
28     B[b0,b1] = B[b1,b0] = A[b0,b1]
29     for i in Q:
30         dd = A[i,closest_i]
31         if dd < d[i]:
32             d[i] = dd
33             pred[i] = closest_i
34 
35   return B

Examples

 1 from numpy import *
 2 from iaprim import iaprim, iaprim2, iaprim3
 3 from iaadjmxtcreate import iaadjmxtcreate
 4 
 5 A = array([[Inf,1.,1.,0.,8.],
 6            [1.,Inf,2.,5.,7.],
 7            [1.,2.,Inf,6.,9.],
 8            [0.,5.,6.,Inf,10.],
 9            [8.,7.,9.,10.,Inf]])
10 random.seed(0)
11 A = random.random_integers(0,10,(6,6))
12 A = maximum(A,A.transpose())
13 
14 print A
15 B = iaprim(A)
16 C = iaprim2(A)
17 D = iaprim3(A)
18 print 'B=',B
19 print 'C=',C
20 print 'D=',D
21 mmgraphviz(iaadjmxtcreate(A,0,True))
22 mmgraphviz(iaadjmxtcreate(B,0,True))
[[ 5  3  8  7  9  9]
 [ 3  5  8  8  7  6]
 [ 8  8 10  1  6  7]
 [ 7  8  1  5  9  8]
 [ 9  7  6  9  3  5]
 [ 9  6  7  8  5  3]]
B= [[ Inf   3.  Inf  Inf  Inf  Inf]
 [  3.  Inf  Inf  Inf  Inf   6.]
 [ Inf  Inf  Inf   1.   6.  Inf]
 [ Inf  Inf   1.  Inf  Inf  Inf]
 [ Inf  Inf   6.  Inf  Inf   5.]
 [ Inf   6.  Inf  Inf   5.  Inf]]
C= [[ Inf   3.  Inf  Inf  Inf  Inf]
 [  3.  Inf  Inf  Inf  Inf   6.]
 [ Inf  Inf  Inf   1.   6.  Inf]
 [ Inf  Inf   1.  Inf  Inf  Inf]
 [ Inf  Inf   6.  Inf  Inf   5.]
 [ Inf   6.  Inf  Inf   5.  Inf]]
D= [[ Inf   3.  Inf  Inf  Inf  Inf]
 [  3.  Inf  Inf  Inf  Inf   6.]
 [ Inf  Inf  Inf   1.   6.  Inf]
 [ Inf  Inf   1.  Inf  Inf  Inf]
 [ Inf  Inf   6.  Inf  Inf   5.]
 [ Inf   6.  Inf  Inf   5.  Inf]]
/media/_xsb/iaOPF/iaprim/GRVIZ83536_001.png

/media/_xsb/iaOPF/iaprim/GRVIZ83536_002.png

Checking results

 1 from iaprim import iaprim,iaprim2,iaprim3
 2 
 3 random.seed(0)
 4 A = random.random_integers(0,1000,(400,400))
 5 A = maximum(A,A.transpose())
 6 n = A.shape[0]
 7 for i in range(1):
 8     t = time.time()
 9     B1=iaprim(A)
10     print "Prim - optimized: time elapsed: %f secs" % (time.time()-t)
11     t = time.time()
12     B2=iaprim2(A)
13     print "Prim - loop: time elapsed: %f secs" % (time.time()-t)
14     t = time.time()
15     B3=iaprim3(A)
16     print "Prim - loop - optimizes min: time elapsed: %f secs" % (time.time()-t)
17     v1 = (B1==B2).all()
18     v2 = (B1==B3).all()
19     B1[B1=='Inf'] = 0
20     B2[B2=='Inf'] = 0
21     B3[B3=='Inf'] = 0
22     v3 = sum(B1)==sum(B2)
23     v4 = sum(B1)==sum(B3)
24     print "Checking correct=",v1, v2,v3,v4
25     print "-" * 20
26     if not v1 or not v2:
27         print sum(B1), sum(B2), sum(B3)
28         break
Prim - optimized: time elapsed: 0.053310 secs
Prim - loop: time elapsed: 0.403501 secs
Prim - loop - optimizes min: time elapsed: 0.383078 secs
Checking correct= True True True True
--------------------

Simply changing the root of the MST, changes its final result. However, the sum of the weights is the same, thus the trees are equivalent.

Checking with pathological cases

 1 from numpy import *
 2 from iaprim import iaprim
 3 from iaadjmxtcreate import iaadjmxtcreate
 4 
 5 A = array([[Inf,0.,0.,0.,0.],
 6            [0.,Inf,1.,1.,1.],
 7            [0.,1.,Inf,1.,1.],
 8            [0.,1.,1.,Inf,1.],
 9            [0.,1.,1.,1.,Inf]])
10 print A
11 B = iaprim(A)
12 print B
13 mmgraphviz(iaadjmxtcreate(A,0,True))
14 mmgraphviz(iaadjmxtcreate(B,0,True))
[[ Inf   0.   0.   0.   0.]
 [  0.  Inf   1.   1.   1.]
 [  0.   1.  Inf   1.   1.]
 [  0.   1.   1.  Inf   1.]
 [  0.   1.   1.   1.  Inf]]
[[ Inf   0.   0.   0.   0.]
 [  0.  Inf  Inf  Inf  Inf]
 [  0.  Inf  Inf  Inf  Inf]
 [  0.  Inf  Inf  Inf  Inf]
 [  0.  Inf  Inf  Inf  Inf]]
/media/_xsb/iaOPF/iaprim/GRVIZ83536_003.png

/media/_xsb/iaOPF/iaprim/GRVIZ83536_004.png

1 from courseIA368Q1S2012.rob_biblio2 import randGraph
2 from iaprim import iaprim2
3 #Grafo completo com 100 nós
4 temp = randGraph(100,0.5,'yes')
5 temp2 = iaprim2(temp)
6 res = (temp2 < inf)
/usr/local/lib/python2.6/dist-packages/scikits/__init__.py:1: UserWarning: Module dateutil was already imported from /usr/local/lib/python2.6/dist-packages/matplotlib-1.1.0-py2.6-linux-x86_64.egg/dateutil/__init__.pyc, but /usr/lib/pymodules/python2.6 is being added to sys.path
  __import__('pkg_resources').declare_namespace(__name__)

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/iaprim/testperf.pkl

Autor Funcao A simple   A: rand(6,6)   100 nodes, complete   100 nodes, 0.5   Grafo MST  
iaprim iaprim 0.334 ms 9.0 0.371 ms 21.0 7.775 ms 318.055294457 7.589 ms 624.679654926 0.583 ms 139.0