Function iadijkstra

Description

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

Examples

 1 from iaOPF import *
 2 
 3 A = array([[float('Inf') ,  8,  9,  4,  6,  8],
 4            [ 8           ,  1,  6, 10,  4,  8],
 5            [ 9           ,  6, 10, 10,  3,  6],
 6            [ 4           , 10, 10,  7,  4,  5],
 7            [ 6           ,  4,  3,  4,  2,  6],
 8            [ 8           ,  8,  6,  5,  6,  9]])
 9 seeds = [3, 4]
10 seeds_labels = [1, 2]
11 SPF = iadijkstra(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.   9.   4.   6.   8.]
 [  8.   1.   6.  10.   4.   8.]
 [  9.   6.  10.  10.   3.   6.]
 [  4.  10.  10.   7.   4.   5.]
 [  6.   4.   3.   4.   2.   6.]
 [  8.   8.   6.   5.   6.   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/iadijkstra/GRVIZ74390_001.png

/media/_xsb/iaOPF/iadijkstra/GRVIZ74390_002.png