Function iamstb_and

Synopse

iamstb_and - Find a minimum spanning tree in a weighted graph.

  • g = iamstb_and(W, A)
    • Output
      • g: tuple, (T, weights). T, with shape=(n,2), is a list of the MST edges, and weights is an array of weights for each MST edge.
    • Input
      • W: ndarray, 2D, square. Weighted graph matrix. If A is not specified, W must have value :eq:+Infty where there are no relations.
      • A: ndarray, 2D, square, boolean (optional). Adjacency matrix with 1/True where there is an edge/arc, and 0/False where there is not.

Description

Function iamstb_and() find a minimum spanning tree in a weighted graph. This implementation is based on Boruvka's MST algorithm.

Function Code

 1 def iamstb_and(W, A=None):
 2     from numpy import arange, logical_not, argsort, array, uint32
 3 
 4     if A is None:
 5         A = W!=float('inf')
 6 
 7     n,_ = A.shape
 8     labels = arange(n)
 9     n -= 1
10     T = []
11     while len(T)<n:
12         E = []
13         oldLabels = labels.copy()
14         connectedComponents = set(labels)
15         for i in connectedComponents:
16             nodes = (oldLabels==i).nonzero()[0]
17             orig, dest = A[nodes,:].nonzero()
18             orig = nodes[orig]
19             allowed = logical_not(oldLabels[orig]==oldLabels[dest])
20             orig, dest = (orig[allowed],dest[allowed])
21             weights = W[orig,dest]
22             j = argsort(weights)[0]
23             u,v = (orig[j],dest[j])
24             if not labels[u]==labels[v]:
25                 E.append([u,v,weights[j]])
26                 labels[labels==labels[v]] = labels[u]
27         for e in E:
28             T.append(e)
29     T = array(T)
30     return (T[:,:2].astype(uint32), T[:,2])

Examples

In a small weighted graph.

 1 from iamstb_and import iamstb_and
 2 from time import time
 3 from numpy import array, zeros
 4 
 5 A = array( [[0,1,1,0,0,0,0,0,0],
 6             [1,0,0,0,0,0,0,1,0],
 7             [1,0,0,1,1,0,0,1,0],
 8             [0,0,1,0,0,0,0,1,0],
 9             [0,0,1,0,0,1,1,0,0],
10             [0,0,0,0,1,0,1,0,1],
11             [0,0,0,0,1,1,0,0,1],
12             [0,1,1,1,0,0,0,0,0],
13             [0,0,0,0,0,1,1,0,0]], dtype=byte)
14 
15 W = array( [[0,1,2,0,0,0,0,0,0],
16             [1,0,0,0,0,0,0,3,0],
17             [2,0,0,4,5,0,0,6,0],
18             [0,0,4,0,0,0,0,7,0],
19             [0,0,5,0,0,8,9,0,0],
20             [0,0,0,0,8,0,1,0,2],
21             [0,0,0,0,9,1,0,0,3],
22             [0,3,6,7,0,0,0,0,0],
23             [0,0,0,0,0,2,3,0,0]], dtype=byte)
24 
25 t = time()
26 T, weights = iamstb_and(W,A)
27 print 'MST edges:\n', T
28 print 'MST weight: ', sum(weights)
29 print 'Computational time: ', time() - t
MST edges:
[[0 1]
 [2 0]
 [3 2]
 [4 2]
 [5 6]
 [7 1]
 [8 5]
 [5 4]]
MST weight:  26
Computational time:  0.00159192085266

Performance Tests

This function is tested by running the tests defined at the page MST Test.

/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__)

System Message: WARNING/2 (<string>, line 121)

Definition list ends without a blank line; unexpected unindent.

<type 'numpy.float64'>

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

Autor Funcao A simple   A: rand(6,6)   100 nodes, complete   100 nodes, 0.5   Grafo MST  
Andre iamstb_and 0.304 ms 9.0 0.447 ms 21.0 11.756 ms 318.055294457 9.452 ms 624.679654926 0.623 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

Contributions

  • André Costa, 1o semestre de 2012.