Python: Liste aller möglichen Pfade in einem Diagramm, das durch das Wörterbuch dargestellt wird

Question

Ich habe ein Wörterbuch mit Schlüsseln, die Knoten und Werte darstellen, die mögliche Knoten darstellen, auf die der Schlüssel zugreifen kann.

Beispiel:

dependecyDict = { 'A': ['D'], 'B': ['A', 'E'], 'C': ['B'], 'D': ['C'], 'G':['H']} 

Ich möchte ein neues dicitonary erstellen, ChainsDict, die alle ‚Werte‘ enthalten, die jeder ‚Schlüssel‘, um mittels dependecyDict durchqueren können.

Zum Beispiel wird die Ausgabe des Programms mit diesem Beispiel sein:

ChainsDict = {'A': ['D', 'C', 'B','E'], 'B':['A','D','C','E'], 'C':['B','A','D','E'], 'D':['C','B','A','E'], 'G': ['H']} 

Ich denke, einen rekursiven Algorithmus verwendet, ist der beste Weg, um eine Lösung zu gehen darum, und ich versuchte, einen kürzesten Weg zu modifizieren durchquert Algorithmus wie folgt:

def helper(dependencyDict, ChainsDict):path = [] 
    for key in dependencyDict: 
     path = path + [(recursiveRowGen(dependencyDict,key))] 
    for paths in path: 
     ChainsDict[paths[0]] = paths[1:] 
    print(finalLineDict) 
def recursiveRowGen(dependencyDict,key,path = []): 
    path = path + [key] 

     if not key in dependencyDict: 
     print("no key: ",key) 
     return path 
     print(dependencyDict[key]) 
     for blocking in dependencyDict[key]: 
      if blocking not in path: 
       newpath = recursiveRowGen(dependencyDict,blocking,path) 
       if newpath: 
        return newpath    
    return path 

Dieser Code hat jedoch Probleme beim Erfassen der richtigen Ausgabe, wenn ein Schlüssel in AbhängigkeitDict mehr als einen Wert hat. Ich fand eine Hacky-Lösung, aber es fühlt sich nicht sehr elegant an. Jede Hilfe wird geschätzt, danke!

Answer 1

Dies ist im Grunde ein Graph Traversal Problem. Sie können jeden Ihrer Schlüssel als Knoten in einem Diagramm darstellen, und seine Werte sind die Knoten, mit denen er verbunden ist.

Sie können entweder eine Tiefensuche oder eine Breitensuche nach einem Diagramm durchführen. Natürlich gibt es auch eine iterative und eine rekursive Lösung für jede dieser Methoden. Hier ist eine iterative Implementierung (ich einige conditionals hinzugefügt Schleifen zu beseitigen):

dependencyDict = { 'A': ['D'], 'B': ['A', 'E'], 'C': ['B'], 'D': ['C'], 'G':['H'] } 
chainsDict = {} 

for key in dependencyDict: 
    currKey = key 
    frontier = [key] 
    visited = [] 
    while frontier: 
     currKey = frontier[0] 
     frontier.remove(currKey) 
     if dependencyDict.get(currKey,0) and (currKey not in visited) and (currKey not in frontier): 
      nodes = dependencyDict[currKey] 
      frontier.extend(nodes) 
      visited.append(currKey) 
     elif currKey in visited: 
      visited.remove(currKey) 
     elif dependencyDict.get(currKey,0) == 0: 
      visited.append(currKey) 
    for i in visited: 
     if i == key: 
      visited.remove(i) 
    chainsDict[key] = visited 

print chainsDict 

Das Ergebnis sieht so aus:

{'A': ['D', 'C', 'B', 'E'], 'C': ['B', 'A', 'E', 'D'], 'B': ['A', 'E', 'D', 'C'], 'D': ['C', 'B', 'A', 'E'], 'G': ['H']} 

Answer 2

hier eine rekursive Lösung ist:

-Code

def get_chain_d(argDict): 
    def each_path(i,caller_chain): 
     a=[] 
     caller_chain.append(i) 
     b = argDict.get(i,[]) 
     for j in b: 
      if j not in caller_chain: 
       a.append(j) 
       a.extend(each_path(j,caller_chain)) 
     return a 

    return {i:each_path(i,[]) for i in argDict} 

dependecyDict = { 'A': ['D'], 'B': ['A', 'E'], 'C': ['B'], 'D': ['C'], 'G':['H']} 

print(get_chain_d(dependecyDict)) 

Ausgabe:

{'B': ['A', 'D', 'C', 'E'], 'A': ['D', 'C', 'B', 'E'], 'D': ['C', 'B', 'A', 'E'], 'C': ['B', 'A', 'D', 'E'], 'G': ['H']}