# Description

Finds the regional minima given a graph with weighted nodes. The regional minima are connected components with a common node value, where all nodes connected to nodes in this component have node values strictly higher.

# Synopse

Returns a tuple with the index of the nodes of regional minima and the labels of its components.

• M = iaminreg(A, W)
• A: the adjacency matrix of a graph (edge values are not used, only indicate the connectivity)
• W: the weights of nodes

# Code

``` 1 def iaminreg(A, W):
2
3     A = A.astype('float')
4     A[arange(len(A)),arange(len(A))] = 1e400
5
6     UNVISITED = 0
7     PENDING = 1
8     VISITED = 2
9
10     work = W.copy()
11     work[:] = UNVISITED
12
13     qPending = list()
14     minima = list()
15     labels = list()
16
17     count = 0
18
19     for (p,pval) in enumerate(W):
20         if work[p] != UNVISITED:
21             continue
22
23         qPending.append(p)
24         work[p] = PENDING
25
26         is_minima = True
27         qMinima = list()
28
29         while not len(qPending) == 0:
30
31             q = qPending.pop(0)
32             qMinima.push(q)
33             work[q] = VISITED
34
35             N = nonzero(A[q])[0]
36
37             for u in N(q):
38
39                 if W[u] == W[q] and work[u] == UNVISITED:
40                     work[u] = PENDING
41                     qPending.push(u)
42                 elif W[u] < W[q]:
43                     is_minima = False # keep flooding the plateau
44
45         if is_minima:
46             count += 1
47             while not len(qMinima) == 0:
48                 q = qMinima.pop(0)
49                 minima.append(q)
50                 labels.append(count)
51
52     return minima, labels
```