Function iadijkstratz

Description

Find the TZ-SPF-Max (Tie-Zone Shortest Path Forest with max cost) of a given graph, represented by its adjacency matrix, with seeds as the roots of the forest.

Synopse

Creates the SPF of a graph represented by its weighted adjacency matrix.

  • SPF = iadijkstratz(A, seeds, seeds_labels)
    • A: the adjacency matrix of a graph
    • seeds: the indices of the nodes to be used as seeds of the SPF-Max
    • seeds_labels: the labels of the seeds

Code

 1 TIE_ZONE = -1
 2 
 3 def iadijkstratz(A, seeds, seeds_labels):
 4     """
 5     Parameters:
 6         A: the adjacency matrix of a graph
 7         seeds: the indices of the nodes to be used as seeds of the SPF-Max
 8 
 9     """
10     from numpy import zeros, ones
11     from heapq import heappush, heappop, heapify
12 
13     n = A.shape[0]
14     done = zeros(n).astype('bool')
15     c1  = ones(n) * float("inf")
16     par = ones(n) * -1
17     lab = ones(n) * float("inf")
18     heap = []
19     for i, v0 in enumerate(seeds):
20         w = 0
21         c1[v0] = w
22         par[v0] = v0
23         lab[v0] = seeds_labels[i]
24         heappush(heap, (w, v0))
25 
26     while len(heap) > 0:
27         (w,p) = heappop(heap)
28         done[p] = True
29         for q in xrange(n):
30             if p == q or done[q]:
31                 continue
32 
33             c = max(c1[p], A[p,q])
34             if c < c1[q]:
35                 if c1[q] < float("inf"):
36                     try:
37                         heap.remove((c1[q], q))
38                         heapify(heap)
39                     except:
40                         pass
41                 c1[q]  = c
42                 par[q] = p
43                 lab[q] = lab[p]
44                 heappush(heap, (c1[q], q))
45             elif c == c1[q] and lab[q] != lab[p]:
46                 lab[q] = TIE_ZONE
47 
48     return c1, par, lab

Examples

 1 from iaOPF import *
 2 
 3 A = array([[float('Inf') ,  8,  8,  4,  6,  8],
 4            [ 8           ,  1,  6, 10,  4,  8],
 5            [ 8           ,  6, 10, 10,  3,  5],
 6            [ 4           , 10, 10,  7,  4,  5],
 7            [ 6           ,  4,  3,  4,  2,  5],
 8            [ 8           ,  8,  5,  5,  5,  9]])
 9 seeds = [3, 4]
10 seeds_labels = [1, 2]
11 SPF = iadijkstratz(A, seeds, seeds_labels)
12 print A
13 print 'costs to root: ', SPF[0]
14 print 'parents: ', SPF[1]
15 print 'labels: ', SPF[2]
16 B = iaadjmtxfromarb(SPF[1], A)
17 mmgraphviz(iaadjmxtcreate(A,dist=True))
18 mmgraphviz(iaadjmxtcreate(B,dist=True))
[[ Inf   8.   8.   4.   6.   8.]
 [  8.   1.   6.  10.   4.   8.]
 [  8.   6.  10.  10.   3.   5.]
 [  4.  10.  10.   7.   4.   5.]
 [  6.   4.   3.   4.   2.   5.]
 [  8.   8.   5.   5.   5.   9.]]
costs to root:  [ 4.  4.  3.  0.  0.  5.]
parents:  [ 3.  4.  4.  3.  4.  3.]
labels:  [ 1.  2.  2.  1.  2. -1.]
/media/_xsb/iaOPF/iadijkstratz/GRVIZ74602_001.png

/media/_xsb/iaOPF/iadijkstratz/GRVIZ74602_002.png