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