Obtenir les chemins possibles

Question

Je dispose d'une structure de données simple représentant les nœuds d'un graphe orienté :

{
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')]
}

J'aimerais obtenir tous les chemins (dirigés) possibles de V1 à Z. Par exemple, un chemin pourrait être :

[
    ('V1', 'R1'),
    ('R1', 'R2'),
    ('R2', 'R4'),
    ('R4', 'Z1')
]

Pourtant, j'ai des difficultés avec ce qui semble être un algorithme de base, qui, je crois, implique une récursivité.

for node, connections in nodes.items():
    for connection in connections:

J'ai commencé par quelque chose comme ce qui précède, mais je pense que ce n'est pas la bonne approche. Quelle serait la manière suggérée de faire cela, sans utiliser quelque chose comme itertools ?

Answer 1

Vous pouvez utiliser la récursivité avec un générateur :

data = {'node1': [('V1', 'R1')], 'node2': [('R1', 'R2'), ('R1', 'R3')], 'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')], 'node4': [('R4', 'Z1')], 'node5': [('R5', 'Z1')]}
new_data = [i for b in data.values() for i in b]
def lookup(start, end, seen=[], c = []):
   _r = [(a, b) for a, b in new_data if a == start and a not in seen]
   for a, b in _r:
      if b == end:
         yield c+[(a, b)]
      else:
         yield from lookup(b, end, seen=seen+[start], c=c+[(a, b)])

print(list(lookup('V1', 'Z1')))

Sortie :

[
  [('V1', 'R1'), 
   ('R1', 'R2'), 
   ('R2', 'R4'), 
   ('R4', 'Z1')], 
  [('V1', 'R1'),  
   ('R1', 'R2'), 
   ('R2', 'R5'), 
   ('R5', 'Z1')], 
  [('V1', 'R1'), 
   ('R1', 'R3'), 
   ('R3', 'R4'), 
   ('R4', 'Z1')], 
  [('V1', 'R1'), 
   ('R1', 'R3'), 
   ('R3', 'R5'), 
   ('R5', 'Z1')]
]