Python list of lists recursion adds extra nesting

Question

I'm trying to solve a similar problem to the one listed here: Python: Combinations of parent-child hierarchy

graph = {}

nodes = [
('top','1a'),
('top','1a1'),
('top','1b'),
('top','1c'),
('1a','2a'),
('1b','2b'),
('1c','2c'),
('2a','3a'),
('2c','3c'),
('3c','4c')
]

for parent,child in nodes:
    graph.setdefault(parent,[]).append(child)

def find_all_paths(graph, start, path=[]):
    path = path + [start]

    if not graph.has_key(start):
        return path

    paths = []

    for node in graph[start]:
        paths.append(find_all_paths(graph, node, path))

    return paths

test = find_all_paths(graph, 'top')

Desired Output:

[['top', '1a', '2a', '3a'],
 ['top', '1a1'],
 ['top', '1b', '2b'],
 ['top', '1c', '2c', '3c', '4c']]

Actual Output:

[[[['top', '1a', '2a', '3a']]],
 ['top', '1a1'],
 [['top', '1b', '2b']],
 [[[['top', '1c', '2c', '3c', '4c']]]]]

Any advice on how I can remove the extra nesting? Thanks!

@TigerhawkT3 that's not the same issue! even if you'll modify: `test = find_all_paths(graph, 'top')` to `test = find_all_paths(graph, 'top', [])` you'll get the same issue — Nir Alfasi, Jan 24 '17 at 05:00
This has nothing to do with the default argument as the argument is not mutated within the confines of the function because of the first assignment. I am voting to reopen this question. — 2ps, Jan 24 '17 at 05:01
Yeah, I'll reopen it. I think TigerhawkT3 was a bit reckless here. — wim, Jan 24 '17 at 05:02
_"This question was marked as a duplicate, but I believe that the issue has to do with the recursive step rather than the default argument. Please correct me if I'm mistaken."_ - No you are correct. The dupe target your question was marked as was incorrect. — Christian Dean, Jan 24 '17 at 05:18
FWIW, the `dict` docs recommend using `in` rather than the `.has_key` method, i.e., `if start not in graph:`. — PM 2Ring, Jan 24 '17 at 05:44
What `has_key`? `AttributeError: 'dict' object has no attribute 'has_key'`! — Antti Haapala -- Слава Україні, Jan 24 '17 at 16:20
Please stop using `has_key`, it was deprecated [**15 years ago**](https://www.python.org/dev/peps/pep-0290/#testing-dictionary-membership). — Antti Haapala -- Слава Україні, Jan 24 '17 at 16:27

2ps · Answer 1 · 2017-01-24T18:13:30.100

The following should fix your issue:

 def find_all_paths(graph, start, path=None):
    if path is None: 
        # best practice, avoid using [] or {} as
        # default parameters as @TigerhawkT3 
        # pointed out.
        path = []
    path = path + [start]

    if not graph.has_key(start):
        return [path] # return the path as a list of lists!

    paths = []
    for node in graph[start]:
        # And now use `extend` to make sure your response
        # also ends up as a list of lists
        paths.extend(find_all_paths(graph, node, path))

    return paths

Blckknght · Accepted Answer · 2017-01-24T05:44:08.753

3

The issue is confusion between path which is a single list, and paths, which is a list of lists. Your function can return either one, depending on where you are in the graph.

You probably want to return a list of paths in all situations. So change return path in the base case to return [path].

In the recursive case, you now need to deal with merging each child's paths together. I suggest using paths.extend(...) instead of paths.append(...).

Putting that all together, you get:

def find_all_paths(graph, start, path=[]):
    path = path + [start]

    if not graph.has_key(start):
        return [path]

    paths = []

    for node in graph[start]:
        paths.extend(find_all_paths(graph, node, path))

    return paths

edited Jan 24 '17 at 05:44

answered Jan 24 '17 at 05:08

Blckknght

100,903
11
120
169

A much better explanation than I offered. +1 – 2ps Jan 24 '17 at 05:18
@Andrew: Whoops, yes, that's a typo. I've edited it. Sorry about that. I suppose this is a good example of the danger of having variables with very similar names. – Blckknght Jan 24 '17 at 05:45

score 0 · Answer 3 · answered Jan 24 '17 at 06:08

Here's a non-recursive solution. However, it "cheats" by sorting the output lists.

def find_all_paths(edges):
    graph = {}
    for u, v in edges:
        if u in graph:
            graph[v] = graph[u] + [v]
            del graph[u]
        else:
            graph[v] = [u, v]
    return sorted(graph.values())

data = (
    ('top','1a'),
    ('top','1a1'),
    ('top','1b'),
    ('top','1c'),
    ('1a','2a'),
    ('1b','2b'),
    ('1c','2c'),
    ('2a','3a'),
    ('2c','3c'),
    ('3c','4c'),
)

test = find_all_paths(data)
for row in test:
    print(row)

output

['top', '1a', '2a', '3a']                                                                                                                      
['top', '1a1']                                                                                                                                 
['top', '1b', '2b']                                                                                                                            
['top', '1c', '2c', '3c', '4c']

Python list of lists recursion adds extra nesting

3 Answers3