Function iaminreg

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

Examples