Python Liste von Listen Rekursion fügt zusätzliche Verschachtelung

Question

Ich versuche, ein ähnliches Problem wie die hier aufgeführt zu lösen: 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') 

gewünschte Ausgabe:

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

tatsächlicher Ausgang:

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

Irgendwelche Ratschläge, wie ich die zusätzliche Verschachtelung entfernen kann? Vielen Dank!

Answer 1

Das Problem ist, Verwirrung zwischen path, die eine einzige Liste ist, und paths, die eine Liste von Listen. Je nachdem, wo Sie sich in der Grafik befinden, kann Ihre Funktion eine davon zurückgeben.

Wahrscheinlich möchten Sie in allen Situationen eine Liste mit Pfaden zurückgeben. Ändern Sie daher return path im Basisfall zu return [path].

Im rekursiven Fall müssen Sie nun die einzelnen Pfade des Kindes zusammenführen. Ich schlage vor, paths.extend(...) anstelle von paths.append(...) zu verwenden.

Putting, dass alle zusammen, erhalten Sie:

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 

Answer 2

Folgendes sollte Ihr Problem beheben:

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 

Answer 3

Hier ist eine nicht-rekursive Lösung. Es "schummelt" jedoch durch Sortieren der Ausgabelisten.

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) 

Ausgang

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