# Description

Finds the nodes of a given graph that are connected directly to nodes with different labels. This is used to find seeds on an MST that ensure that on the calculation of the SPF-Max using these seeds, the labels of the nodes will be the same as of input. This is also known as finding the minimal set of seeds for a given segmentation.

# Synopse

Create a list of indices that represent the nodes selected as seeds.

• seeds = iamstseeds(MST, labels)
• MST: the adjacency matrix of the graph that represents the MST
• labels: the vector that has the labels of each node of the graph
``` 1 def iamstseeds(MST, labels):
2     """
3     Parameters:
4         MST: the adjacency matrix of the graph that represents the MST
5         labels: the vector that has the labels of each node of the graph
6
7     >>> from numpy import array
8     >>> MST = array([[inf, inf, inf,   4, inf, inf],
9                      [inf, inf, inf, inf,   4, inf],
10                      [inf, inf, inf, inf,   3, inf],
11                      [  4, inf, inf, inf,   4,   5],
12                      [inf,   4,   3,   4, inf, inf],
13                      [inf, inf, inf,   5, inf, inf]])
14
15     >>> labels = [1, 2, 2, 1, 2, 1]
16     >>> iamstseeds(MST, labels)
17     [3, 4]
18     >>>
19     """
20
21     from numpy import where, array
22
23     n = MST.shape[0]
24     if n != len(labels):
25         return []
26
27     seeds = []
28
29     for i in range(n):
30         w = MST[i,:]
31         wix = where(w != float("inf"))[0]
32         l = array(map(lambda x: labels[x], wix))
33         #wl = float(sum(l))/float(len(l))
34         lmin = l.min()
35         lmax = l.max()
36
37         if l.min()!=l.max():
38            seeds.append(i)
39         elif lmin!= labels[i]:
40             seeds.append(i)
41
42     return seeds
```

# Examples

## Example 1

``` 1 from numpy import array
2 from iaOPF import *
3 inf = float("inf")
4 MST = array([[inf, inf, inf,   4, inf, inf],
5              [inf, inf, inf, inf,   4, inf],
6              [inf, inf, inf, inf,   3, inf],
7              [inf, inf, inf, inf,   4,   5],
8              [inf,   4,   3,   4, inf, inf],
9              [inf, inf, inf,   5, inf, inf]])
10 labels = [1, 2, 2, 1, 2, 1]
11 seeds = iamstseeds(MST, labels)
12 print seeds
```
```[3, 4]
```

## Example 2

``` 1 from numpy import *
2 from iaprim import iaprim
3 from iaadjmxtcreate import iaadjmxtcreate
4 from iamstseeds import iamstseeds
5
6 adj_matrix = array([[inf,1,3,4],
7                     [1,inf,2,5],
8                     [3,2,inf,6],
9                     [4,5,6,inf]])
10
11 label_vector = array([0,0,0,1])
12
13 print 'Adjacent Matrix \n',adj_matrix
14 MST = iaprim(adj_matrix)
15 print 'MST \n',MST
16 mmgraphviz(iaadjmxtcreate(adj_matrix,dist=True), title='Adjacent Matrix')
17 mmgraphviz(iaadjmxtcreate(MST,dist=True),title='MST')
18
19 seeds = iamstseeds(MST,label_vector)
20 print 'seeds: \n',seeds
```
```Adjacent Matrix
[[ Inf   1.   3.   4.]
[  1.  Inf   2.   5.]
[  3.   2.  Inf   6.]
[  4.   5.   6.  Inf]]
MST
[[ Inf   1.  Inf   4.]
[  1.  Inf   2.  Inf]
[ Inf   2.  Inf  Inf]
[  4.  Inf  Inf  Inf]]
seeds:
[0, 3]
```

## Example 3

``` 1 from numpy import *
2 from iaprim import iaprim
3 from iaadjmxtcreate import iaadjmxtcreate
4 from iamstseeds import iamstseeds
5
6 adj_matrix = array([[inf,inf,inf,inf,0.88],
7                     [inf,inf,inf,1.97,1.06],
8                     [inf,inf,inf,1.97,inf],
9                     [inf,1.97,1.97,inf,inf],
10                     [0.88,1.06,inf,inf,inf]])
11
12 label_vector = array([2,1,0,1,2])
13
14 print 'Adjacent Matrix \n',adj_matrix
15 MST = iaprim(adj_matrix)
16 print 'MST \n',MST
17 mmgraphviz(iaadjmxtcreate(adj_matrix, dist=True), title='Adjacent Matrix')
18 mmgraphviz(iaadjmxtcreate(MST,dist=True),title='MST')
19
20 seeds = iamstseeds(MST,label_vector)
21 print 'seeds: \n',seeds
```
```Adjacent Matrix
[[  Inf   Inf   Inf   Inf  0.88]
[  Inf   Inf   Inf  1.97  1.06]
[  Inf   Inf   Inf  1.97   Inf]
[  Inf  1.97  1.97   Inf   Inf]
[ 0.88  1.06   Inf   Inf   Inf]]
MST
[[  Inf   Inf   Inf   Inf  0.88]
[  Inf   Inf   Inf  1.97  1.06]
[  Inf   Inf   Inf  1.97   Inf]
[  Inf  1.97  1.97   Inf   Inf]
[ 0.88  1.06   Inf   Inf   Inf]]
seeds:
[1, 2, 3, 4]
```