# 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]
```[[ Inf   8.   9.   4.   6.   8.]