# Synopse

iadijkstra_and - Compute an Optimum Path Forest in a weighted graph.

• g = iadijkstra_and(W, A, seeds, handcaps, costFunction)
• Output
• g: tuple, (roots, predecessors, costs). Tuple with three array elements with size=graph order: roots, the root of each graph node; predecessors, the predecessor of each graph node; and costs, for each graph node, the optimum path cost to its root.
• Input
• W: ndarray, 2D, square. Weighted graph matrix. If A is not specified, W must have value :eq:+Infty where there are no relations.
• A: ndarray, 2D, square, boolean (optional). Adjacency matrix with 1/True where there is an edge/arc, and 0/False where there is not.
• seeds: ndarray, 1D (optional). Graph nodes that are candidates to be the forest roots.
• handcaps: ndarray, 1D (optional). Handcap values for each specified seed.
• costFunction: function, number of arguments=2, return one argument only (optional). Function used to calculate the path cost of a node to one seed. Must be able to process at once multiple entries, i. e., two unidimensional arrays with same size as arguments (in this case, the return must be also an unidimensional array with same size)

# Description

Function iadijkstra_and() compute an Optimum Path Forest in a weighted graph. This implementation is based on the Dijkstra's algorithm.

# Function Code

```  1 def sumCost(s, st):
2     return s+st
3
4 def maxCost(s, st):
5     from numpy import maximum
6
7     return maximum(s,st)
8
9 def iadijkstra_and(W, A=None, seeds=None, handcaps=None, costFunction=maxCost):
10     from numpy import zeros, ones, arange, array, int64
11     from heapq import heappush, heappop
12     from scipy.sparse import lil_matrix, isspmatrix_lil
13
14     if A is None:
15         A = W!=float('inf')
16
17     if seeds is None:
18         seeds = array([0])
19
20     seeds = seeds.astype(int64)
21     m,n = A.shape
22     if not (m==n or A.shape==W.shape):
23         return None
24
25     # sets handcap to ZERO, if ignored
26     if handcaps is None:
27         handcaps = zeros(seeds.shape)
28
29     if isspmatrix_lil(A):
30         sparseA = A
31     else:
32         sparseA = lil_matrix(A)
33
34     # each entry i has a list of neighbors of i
35     neighbors = sparseA.rows
36
37     # sets initial costs to +Infinity for all nodes
38     costs = ones((n,))*float('Inf')
39
40     # sets the cost of each seed as the given handcap, or zero if handcap is ignored
41     costs[seeds] = handcaps
42
43     # sets the predecessor of each node as self
44     predecessors = arange(n)
45
46     # sets the root of each node as self
47     roots = predecessors.copy()
48
50     Q = ones((n,), dtype=bool)
51
52     # min-heap to keep track of the path with lowest cost in the forest
53     pQ = []
54     for s in seeds:
55         heappush(pQ,(costs[s],s))
56
57     # counts how many nodes were processed
58     count = 0
59     while(count<n and len(pQ)>0):
60
61         # lower path cost and its associated node
62         w,s = heappop(pQ)
63
64         # is the node was not processed yet
65         if Q[s]:
66             # mark as processed
67             Q[s] = False
68             count += 1
69
70             # get all neighbors of s as array
71             t = array(neighbors[s], dtype=int64)
72
73             # get the arc cost for each neighbor
74             st_w = W[s,t]
75
76             # path cost until s, for each neighbor
77             s_w = ones(st_w.shape)*w
78
79             # calculate the concatenated path cost for each neighbor
80             cat_w = costFunction(s_w,st_w)
81
82             # select the nodes with less concatenated cost than the old cost
83             selection = cat_w<costs[t]
84             smaller = t[selection]
85
86             if smaller.shape[0]>0:
87                 # update the path cost for each selected node
88                 costs[smaller] = cat_w[selection]
89
90                 # update predecessor for each selected node
91                 predecessors[smaller] = s
92
93                 # update roots for each selected node
94                 roots[smaller] = roots[s]
95
96                 # insert updated costs into heap
97                 cat_w = cat_w[selection]
98                 for i in arange(smaller.shape[0]):
99                     heappush(pQ, (cat_w[i],smaller[i]))
100
101     return (roots,predecessors,costs)
```

# Examples

In a small weighted graph.

``` 1 from numpy import array
3
4 W = array( [[0,51,0,0,151,0,0,0,0,0,0,0,0,0],
5             [51,0,75,0,0,0,0,0,0,0,0,0,0,0],
6             [0,75,0,118,140,0,0,0,0,0,0,0,0,0],
7             [0,0,118,0,0,0,111,0,0,0,0,0,0,0],
8             [151,0,140,0,0,99,0,80,0,0,0,0,0,0],
9             [0,0,0,0,99,0,0,0,0,0,0,0,211,0],
10             [0,0,0,111,0,0,0,0,70,0,0,0,0,0],
11             [0,0,0,0,80,0,0,0,0,0,146,97,0,0],
12             [0,0,0,0,0,0,70,0,0,75,0,0,0,0],
13             [0,0,0,0,0,0,0,0,75,0,120,0,0,0],
14             [0,0,0,0,0,0,0,146,0,120,0,138,0,0],
15             [0,0,0,0,0,0,0,97,0,0,138,0,101,0],
16             [0,0,0,0,0,211,0,0,0,0,0,101,0,90],
17             [0,0,0,0,0,0,0,0,0,0,0,0,90,0]] )
18 A = W>0
19 seeds = array([5,9])
20
21 g = iadijkstra_and(W, A, array([5,9]))
22 print 'roots:'
23 print g[0], '\n'
24 print 'predecessors:'
25 print g[1], '\n'
26 print 'costs:'
27 print g[2], '\n'
```
```roots:
[9 9 9 9 5 5 9 5 9 9 9 5 5 5]

predecessors:
[ 1  2  3  6  5  5  8  4  9  9  9  7 11 12]

costs:
[ 118.  118.  118.  111.   99.    0.   75.   99.   75.    0.  120.   99.
101.  101.]
```

# Performance Tests

This function is tested by running the tests defined at the page Optimum Path Test.

/usr/local/lib/python2.6/dist-packages/scikits/__init__.py:1: UserWarning: Module dateutil was already imported from /usr/local/lib/python2.6/dist-packages/matplotlib-1.1.0-py2.6-linux-x86_64.egg/dateutil/__init__.pyc, but /usr/lib/pymodules/python2.6 is being added to sys.path
__import__('pkg_resources').declare_namespace(__name__)