Python: список всех возможных путей в графике, представленном в словаре

Question

У меня есть словарь с ключами, представляющими узлы и значения, представляющие возможные узлы, к которым может пройти ключ.

Пример:

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

Я хочу создать новую dicitonary, ChainsDict, который будет содержать все «ценности», что каждый «ключ» может траверс с помощью dependecyDict.

Например, выход из программы с этим примером будет:

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

Я думаю, что с помощью рекурсивного алгоритма является лучшим способом идти о принятии решения, и я попытался модифицировать кратчайший путь, пересекающий алгоритм следующим образом:

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 

Этот код, однако возникают проблемы, захватив правильный вывод, когда ключ в dependecyDict имеет более чем одно значение. Я нашел хакерское решение, но оно не очень элегантно. Любая помощь приветствуется, спасибо!

Answer 1

Это в основном проблема обхода графика. Вы можете представить каждый свой ключ как узел в графе, а его значения - узлы, к которым он подключен.

Вы можете выполнить поиск по глубине или по ширине в начале графика. Конечно, есть также итеративное и рекурсивное решение для каждого из этих методов. Вот итеративная реализация (я добавил несколько условных для устранения петель):

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 

Результата выглядит следующим образом:

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

Answer 2

Вот рекурсивное решение:

Код

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)) 

Выход:

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