Вот простой подход - это O (N в квадрате), так что не очень хорошо масштабируемый, но хорошо послужит вам при разумном размере книги (если у вас, скажем, миллионы страниц, вам нужно подумать о совсем другом и менее простом подходе; -).
Во-первых, создайте более удобный для использования диктофон, сопоставляя страницу с набором содержимого: например, если исходный диктат равен d, сделайте еще один диктовку mud как:
mud = dict((p, set(d[p]['contents'].split())) for p in d)
Затем установите dict, отображающий каждую страницу на родительские страницы:
parent = dict((p, [k for k in mud if p in mud[k]]) for p in mud)
Здесь я использую списки родительских страниц (наборы тоже подойдут), но это нормально для страниц с 0 или 1 родителем, как и в вашем примере - вы просто будете использовать пустой список для обозначения "Нет родителя", иначе список с родителем в качестве единственного элемента. Это должен быть ациклический ориентированный граф (если у вас есть сомнения, вы можете проверить, конечно, но я пропускаю эту проверку).
Теперь, для данной страницы, для поиска путей от ее родителя (ов) к родительскому родительскому элементу («корневой странице») просто необходимо «пройти» диктовку parent. Например, в родительском случае 0/1:
path = [page]
while parent[path[-1]]:
path.append(parent[path[-1]][0])
Если вы сможете лучше уточнить свои спецификации (диапазоны количества страниц на книгу, количество родителей на страницу и т. Д.), Этот код, без сомнения, может быть уточнен, но я надеюсь, что для начала он может помочь.
Редактировать : поскольку ФП пояснил, что случаи с> 1 родителем (и, таким образом, несколькими путями) действительно представляют интерес, позвольте мне показать, как с этим справиться:
partial_paths = [ [page] ]
while partial_paths:
path = partial_paths.pop()
if parent[path[-1]]:
# add as many partial paths as open from here
for p in parent[path[-1]]:
partial_paths.append(path + [p])
else:
# we've reached a root (parentless node)
print(path)
Конечно, вместо print ing, вы можете yield каждый путь, когда он достигает корня (превращая функцию, тело которой в генератор), или иным образом обрабатывать его так, как вам нужно.
Снова отредактируйте : комментатор беспокоится о циклах на графике. Если это беспокойство оправдано, нетрудно отслеживать узлы, уже замеченные на пути, а также обнаруживать и предупреждать о любых циклах. Быстрее всего сохранить набор рядом с каждым списком, представляющим частичный путь (нам нужен список для упорядочения, но проверка на членство - это O (1) в наборах против O (N) в списках):
partial_paths = [ ([page], set([page])) ]
while partial_paths:
path, pset = partial_paths.pop()
if parent[path[-1]]:
# add as many partial paths as open from here
for p in parent[path[-1]]:
if p in pset:
print('Cycle: %s (%s)' % (path, p))
continue
partial_paths.append((path + [p], pset.union([p])))
else:
# we've reached a root (parentless node)
print('Path: %s' % (path,))
Вероятно, для ясности целесообразно упаковать список и набор, представляющий частичный путь, в небольшой служебный класс Path с подходящими методами.