Issues with iteration in a recursive function

Question

The code below is used to find the shortest path based on the constraints (of maxTotalDist and maxDistOutdoors) given. I have got it mostly working, but the problem I am having is that even though I am able to find a path (on some given problems). I'm not able to confirm that I've found it.

For example, if a path is found, the "visited" list, in the code, should be the full path that I obtained (the path is then tested on whether or not it is good enough to be the "shortest path"). But, any print statements I try to implement to see which nodes I'm hitting aren't being printed. (i.e. Trying to find the path from Node 'A' to Node 'C', Node A has children ['b', 'c']. If I make the sample if statement (if visited[0] == 'c'), the print statement will not go off).

Anyway, I know this is probably really badly written, but any help would contribute. Thanks.

def bruteForceSearch1(digraph, start, end, maxTotalDist, maxDistOutdoors, visited = [])
    if not (digraph.hasNode(start) and digraph.hasNode(end)):
        raise ValueError('Start or End not in graph')
    path = [str(start)]
    if start == end:
        return path
    shortest = None

    #This is the iterator talked about in the question
    for node in digraph.childrenOf(start):

        if (str(node) not in visited):
            visited = visited + [str(node)]

            #Sample print statement
            if visited[0] == 'nodeName':
                print "Node is part of search"

            newPath = bruteForceSearch1(digraph, node, end, maxTotalDist, maxDistOutdoors, visited)
            if newPath == None:
                continue
            if shortest != None:
                totalShort, outdoorShort = digraph.getDistances(shortest)
            total, outdoor = digraph.getDistances(path + newPath)
            if (total <= maxTotalDist) and (outdoor <= maxDistOutdoors):
                if (shortest == None):
                    shortest = newPath
                else:
                    if (len(newPath) < len(shortest)):
                        shortest = newPath
                    elif (len(newPath) == len(shortest)) and (total <= totalShort) and (outdoor <= outdoorShort):
                        shortest = newPath
    if shortest != None:
        path = path + shortest
    else:
        path = None
    return path

I see a [mutable default](http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument), but you overwrite with `path = [str(start)]` anyways — OneCricketeer, Sep 26 '16 at 22:52
Why not use a modified version of Dijkstra's with two costs? — EvilTak, Sep 27 '16 at 07:13
Okay thanks for notifying me of the mutable default. Apparently the code is "browsing" through the graph. For some reason I am still getting a "none" (no solution w/ the constraints) with this code. It does give solutions for the shortest path if the constraints are open, but if the constraints are tight then it starts having trouble. So, I'll probably just take your advice @Evil Tak and modify a Dijkstra's. — Kellan Martin, Sep 30 '16 at 21:25

score 0 · Answer 1 · answered Sep 30 '16 at 21:25

All of the recursive calls will see the same value as visited[0]. It will always be the first child of the original start value. Since you're appending all other values to the end of the list, nothing will ever replace that child as the first value in visited.

I think you probably want to check your specific name against node instead of against visited[0].

There may be some other issues with your code. For instance, you'll never consider a path a->c->b if the path a->b exists (since b will be in visited after a->b is checked). In some kinds of graphs (where the triangle inequality doesn't hold), the first path might be shorter than the second. If it's not possible in your graph, you could be fine, but it's not something you should assume for all graphs.

Issues with iteration in a recursive function

1 Answers1