Function iaprototype

Description

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

Synopse

Return the prototypes of a weighted matrix MST.

  • prototype_array = iaprototype(A,label_vector)
    • A: Input weighted matrix.
    • label_vector: Input label vector of each node.
    • prototype_array: Output prototype_array that indicate the prototypes.

Code Function

 1 from numpy import *
 2 from iaprim import iaprim
 3 from iaadjmxtcreate import iaadjmxtcreate
 4 
 5 def iaprototype(B, label_vector):
 6     C =  zeros(label_vector.shape[0],int)
 7 
 8     for i in range(B.shape[0]):
 9         for j in range(B.shape[1]):
10 
11             if B[i,j]!=0: # connected nodes
12                 if label_vector[i]!=label_vector[j]: # different labels
13                     C[i] = 1 # is set as a prototype
14                     C[j] = 1 # is set as a prototype
15 
16     return C

Examples

 1 from numpy import *
 2 from iaprim import iaprim
 3 from iaadjmxtcreate import iaadjmxtcreate
 4 from iaprototype import iaprototype
 5 
 6 
 7 A = array([[0,1,3,4],
 8            [1,0,2,5],
 9            [3,2,0,6],
10            [4,5,6,0]])
11 
12 label_vector = array([0,0,0,1])
13 
14 print 'input matrix \n',A
15 B = iaprim(A)
16 print 'MST \n',B
17 mmgraphviz(iaadjmxtcreate(A,dist=True))
18 mmgraphviz(iaadjmxtcreate(B,dist=True))
19 
20 C = iaprototype(B, label_vector)
21 print 'list of prototypes \n',C
input matrix 
[[0 1 3 4]
 [1 0 2 5]
 [3 2 0 6]
 [4 5 6 0]]
MST 
[[ Inf   1.  Inf   4.]
 [  1.  Inf   2.  Inf]
 [ Inf   2.  Inf  Inf]
 [  4.  Inf  Inf  Inf]]
list of prototypes 
[1 1 1 1]
/media/_xsb/iaOPF/iaprototype/GRVIZ74906_001.png

/media/_xsb/iaOPF/iaprototype/GRVIZ74906_002.png