CODEWITHSUNDEEP
pythonrecursionnested-lists
atm
atm

Reputation: 1783

Python list of lists recursion adds extra nesting

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!

Upvotes: 2

Views: 540

Answers (3)

2ps
2ps

Reputation: 15926

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

Upvotes: 4

PM 2Ring
PM 2Ring

Reputation: 55479

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']

Upvotes: 0

Blckknght
Blckknght

Reputation: 104732

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

Upvotes: 3

Related Questions