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.