Граф с несколькими узлами на граф с одним узлом в Python

Question

У меня есть Направленный ациклический граф, что-то вроде этого:

[a, b, c] --> [p, q] --> [p, a, c] --> [x, y, z]

Здесь каждый из алфавитов является узлом. Из приведенного выше графика я хочу получить список всех графиков, имеющих отдельные узлы. например Один график может быть: a --> p --> a --> y Другой может быть: b --> p --> p --> z и т. Д.

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

Answer 1

Если у вас есть список наборов узлов, вы можете сделать что-то вроде этого -

from itertools import product
s =[[1, 2], [3, 4, 5], [6, 7]]
list(product(*s))

output -

[(1, 3, 6), (1, 3, 7), (1, 4, 6), (1, 4, 7), (1, 5, 6), (1, 5, 7), (2, 3, 6), (2, 3, 7), (2, 4, 6), (2, 4, 7), (2, 5, 6), (2, 5, 7)]