Recursive function to search through a dictionary linked to parallel arrays?

Question

I am currently working on a recursive function to search through a dictionary that represents locations along a river. The dictionary indexes 4 parallel arrays using start as the key.

Parallel Arrays:

start = location of the endpoint with the smaller flow accumulation,

end = location of the other endpoint (with the larger flow accumulation),

length = segment length, and;

shape = actual shape, oriented to run from start to end.

Dictionary:

G = {}
for (st,sh,le,en) in zip(start,shape,length,end):
    G[st] = (sh,le,en)

My goal is to search down the river from one of it's start points represented by p and select a locations at 2000 metres (represented by x) intervals until the end. This is the recursive function I'm working on with Python:

def Downstream (p, x, G):
...     e = G[p]
...     if (IsNull(e)):
...         return ("Not Found")
...         if (x < 0):
...             return ("Invalid")
...             if (x < e.length):
...                 return (Along (e.shape, x))
...                 return (Downstream (e.end, x-e.length,G))

Currently when I enter Downstream ("(1478475.0, 12065385.0)", 2000, G) it returns a keyerror. I have checked key in G and the key returns false, but when I search G.keys () it returns all keys represented by start including the ones that give false.

For example a key is (1478475.0, 12065385.0). I've used this key as text and a tuple of 2 double values and keyerror returned both times.

Error:

Runtime error
Trackback (most recent call last):
 File “<string>”, line 1, in <module>
 File “<string>”, line 1, in Downstream
KeyError:  (1478475.0, 12065385.0)

What is causing the keyerror and how can I solve this issue to reach my goal?

I am using Python in ArcGIS as this is using an attribute table from a shapefile of polylines and this is my first attempt at using a recursive function.

This question and answer is how I've reached this point in organizing my data and writing this recursive function.

https://gis.stackexchange.com/questions/87649/select-points-approx-2000-metres-from-another-point-along-a-river

Examples:

>>> G.keys ()
[(1497315.0, 11965605.0), (1502535.0, 11967915.0), (1501785.0, 11968665.0)...

>>> print G
{(1497315.0, 11965605.0): (([1499342.3515172896, 11967472.92330054],), (7250.80302528,), (1501785.0, 11968665.0)), (1502535.0, 11967915.0): (([1502093.6057616705, 11968248.26139775],), (1218.82250994,), (1501785.0, 11968665.0)),...

Answer 1

Your function is not working for five main reasons:

1. The syntax is off - indentation is important in Python;
2. You don't check whether p in G each time Downstream gets called (the first key may be present, but what about later recursive calls?);
3. You have too many return points, for example your last line will never run (what should the function output be?);
4. You seem to be accessing a 3-tuple e = (sh, le, en) by attribute (e.end); and
5. You are subtracting from the interval length when you call recursively, so the function can't keep track of how far apart points should be - you need to separate the interval and the offset from the start.

Instead, I think you need something like (untested!):

 def Downstream(start, interval, data, offset=0, out=None):
     if out is None:
         out = []
     if start in data:
         shape, length, end = data[start]
         length = length[0] 
         if interval < length:
             distance = offset
             while distance < length:
                 out.append(Along(shape, distance))
                 distance += interval
             distance -= interval
             Downstream(end, interval, data, interval - (length - distance), out)
         else:
             Downstream(end, interval, data, offset - length, out)
     return out

This will give you a list of whatever Along returns. If the original start not in data, it will return an empty list.