Function iamstk_thi

Synopse

iamstk_thi runs Kruskal algorithm in a given graph in order to find its MST.

  • output_parameters = iamstk_thi(adjMat, build_adjMat = False)
    • Output

      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).
    • Input
      • 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).

Description

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.

Function Code

 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[0]
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[1]][e[0]] = e[2]
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

Examples

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]])

Performance Tests

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

<type 'numpy.float64'>

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

References

[Feof2009]Paulo Feofiloff. Algoritmos para Grafos em C via Sedgewick. IME-USP. http://www.ime.usp.br/~pf/algoritmos_para_grafos

Contributions

  • Thiago José, 1o semestre de 2012.