# 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.