# Function iadijkstra_and

# 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
49 # maintain information about alread processed nodes
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
2 from iadijkstra_and import iadijkstra_and
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__)

gravando arquivo: /home/rubens/www/media/Attachments/iaOPF/iadijkstra_and/testperf.pkl

Autor | Funcao | Simple Test Graph | Complete(v =50) | Complete(v =100) | 3 connected components | ||||
---|---|---|---|---|---|---|---|---|---|

Andre | iadijkstra_and | 1.363 ms | 41.0 | 5.371 ms | 488.129970057 | 13.14 ms | 417.759426795 | 1.245 ms | inf |

# Contributions

- André Costa, 1o semestre de 2012.