strange result from yield from in python

Question

I have a depth-first search example code in python as below.

def DFS_paths_recursive(self, start, end, path = None):
    if path == None:
        path = [start]
    if start == end:
        yield path
    else:
        unvisited = set(self._graph_dic[start]) - set(path)
        for vertex in unvisited:
            yield from self.DFS_paths_recursive(vertex, end, path+[vertex])

But if I modify the code as below, the output is strange. What I did is just modifying the path before the recursive call in the last line. What is the problem?

def DFS_paths_recursive(self, start, end, path = None):
    if path == None:
        path = [start]
    if start == end:
        yield path
    else:
        unvisited = set(self._graph_dic[start]) - set(path)
        for vertex in unvisited:
            path.append(vertex)
            yield from self.DFS_paths_recursive(vertex, end, path)

For example, for the graph g = { "a" : ["d"], "b" : ["c"], "c" : ["b", "c", "d", "e"], "d" : ["a", "c", "e"], "e" : ["c"], "f" : ["g"], "g" : ["f"] } Sometimes the output of paths between "a" and "e" is ['a', 'd', 'c', 'b', 'e'],['a', 'd', 'c', 'b', 'e', 'e'], and sometimes the output becomes ['a', 'd', 'e'].

"But if I modify the code as below, the output is strange." - "strange" isn't a useful error description. Please provide more detail, perhaps including actual program output. — user2357112, Oct 22 '15 at 21:37
Yield might not do what you expect. Have you seen this page? http://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python — McGlothlin, Oct 22 '15 at 21:41

score 0 · Answer 1 · answered Oct 23 '15 at 03:59

This has nothing to do with yield from. When you do path.append(vertex), you mutate the original copy of path (which means the version your caller passed you, and the version you pass to the recursive call). Even within the function, it's behaving differently, since repeated appends mean each recursive call is handling all the same values as the last plus one more, instead of a fixed base path plus a single additional value on each loop.

Doing path+[vertex] is creating a new list to pass to the recursive call, preventing mutations from affecting your own copy of path, and only adding one new value to the base path for each recursive call without changing the base path.

strange result from yield from in python

1 Answers1