iamstk_thi runs Kruskal algorithm in a given graph in order to find its MST.
- output_parameters = iamstk_thi(adjMat, build_adjMat = False)
The output can be one of the following depending on argument build_adjMat:
- adjancency matrix: Numpy array. MST adjancency matrix (build_adjMat = True).
- edges list: List. List of tuples. Each tuple represents an edge from the found MST. The tuple is composed by the two nodes index that form the edge and the cost of the latter (build_adjMat = False).
- adjMat: Numpy array. Graph adjacency matrix whose MST shall be evaluated.
- build_adjMat: bool. Specify if function should return a list of edges (False) or the MST adjancency matrix (True).
The class Forest is an auxiliary structure used inside iamstk_thi function for making union operations. It represents a forest and has an internal list where each element represents a tree. It's constructed by passing a list with all node indexes, thus in its initial state, it has as trees as there are nodes.
The method joinTrees associates a node with other, therefere merging two trees.
The method find finds the parent node or the last node which is merged with the given node. The former is a unique node index which represent the tree/forest which the given node is inserted in.
iamstk_thi function first create two lists. One with node indexes and other which is filled with as tuples as edges in the graph. Each tuple is composed by the nodes index that form a edge and its cost, which we will call graph list of edges
Than it's created an object from class Forest and an empty list, analog to the just above mentioned list of tuples, except for having only edges of the target MST. Therefore this list is filled along algorithm, which we will call MST list of edges
Later, the graph list of edges is sorted and the tuples are successively grabbed by smallest associated cost order. Its node indexes are passed to method find of class Forest to find out which tree each of these nodes are associated to. If they are related to different trees, they are joined through method joinTrees and the current tuple is pushed to the MST list of edges.
When the MST list of edges reach the size of nodes in the graph, the process is stopped.
Finally, depending on argument build_adjMat, it's returned to the user the MST list of edges or a adjacency matrix related to the MST.
1 from numpy import * 2 import operator as op 3 4 5 class Forest(dict): 6 def __init__(self, nodes): 7 for v in nodes: 8 self[v] = v 9 10 def find(self, item): 11 parent = self[item] 12 13 while self[parent] != parent: 14 parent = self[parent] 15 16 self[item] = parent 17 return parent 18 19 def joinTrees(self, item1, item2): 20 self[item2] = self[item1] 21 22 23 def iamstk_thi(adjMat, build_adjMat = False): 24 nV = adjMat.shape 25 nodes = range(nV) 26 edges =  27 28 # find edges 29 upM = triu(adjMat) 30 idY, idX = where(upM != 0) 31 32 # build list of edges (tuples with node index and edge cost) 33 for x,y in zip(idX,idY): 34 if x != y: 35 edges.append((x,y,upM[y][x])) 36 37 # start kruskal algorithm 38 forest = Forest(nodes) 39 mst =  40 # sort edges and pick them from the smallest 41 for e in sorted( edges, key = op.itemgetter( 2 ) ): 42 if len(mst) != nV: 43 n1, n2, _ = e 44 t1 = forest.find(n1) 45 t2 = forest.find(n2) 46 if t1 != t2: 47 mst.append(e) 48 forest.joinTrees(t1, t2) 49 else: 50 break 51 52 if build_adjMat: 53 mat = zeros((nV,nV), dtype=float) 54 for e in mst: 55 mat[e][e] = e 56 57 mat = triu(mat) 58 mat = mat + mat.transpose() 59 mat = where(mat == 0., inf, mat) 60 return mat 61 else: 62 return mst
Example 1: Graph with 4 nodes
1 from iamstk_thi import iamstk_thi 2 from numpy import array, inf 3 4 grafo1 = array([ [inf, 6.0, inf, 5.0 ], [6.0, inf, 4.0, inf], [inf, 4.0, inf, inf], [inf, 5.0, inf, inf]]) 5 print 'MST list of edges:\n', iamstk_thi(grafo1, False).__repr__() 6 print 'MST adjacency matrix:\n', iamstk_thi(grafo1, True).__repr__()
MST list of edges: [(2, 1, 4.0), (3, 0, 5.0), (1, 0, 6.0)] MST adjacency matrix: array([[ Inf, 6., Inf, 5.], [ 6., Inf, 4., Inf], [ Inf, 4., Inf, Inf], [ 5., Inf, Inf, Inf]])
This function is tested by running the tests defined at the page MST Test.
1 from iamcc_test import objTestes_inf 2 from numpy import inf 3 4 objTestes_inf.setup(xsPackage, xsModule) 5 6 listF =  7 listPP =  8 9 posproc_1 = lambda x,y: y[y!=Inf].sum()/2 10 listPP.append(posproc_1) 11 12 fnc_1 = ['Thiago', 'iamstk_thi', lambda x:iamstk_thi(x, True), listPP] 13 listF.append(fnc_1) 14 15 objTestes_inf.runTests(listF)
gravando arquivo: /home/rubens/www/media/Attachments/iaOPF/iamstk_thi/testperf.pkl
|Autor||Funcao||A simple||A: rand(6,6)||100 nodes, complete||100 nodes, 0.5||Grafo MST|
|Thiago||iamstk_thi||0.237 ms||14.0||0.257 ms||21.0||52.639 ms||318.055294457||58.411 ms||8153.94473627||0.781 ms||61.0|
|[Feof2009]||Paulo Feofiloff. Algoritmos para Grafos em C via Sedgewick. IME-USP. http://www.ime.usp.br/~pf/algoritmos_para_grafos|
- Thiago José, 1o semestre de 2012.