Множественные деревья и сооружения

Question

У меня есть проблема в прикладной математике, которая может быть почти идеально сопоставлена ​​с нахождением самого длинного пути в многоликом дереве.

У меня есть функция child(), которая дает дочерние узлы (точки в пространстве, удовлетворяющие условию). Единственное предостережение в том, что для child() требуются все предыдущие узлы, подключенные к нему, включая корневой узел. Именно здесь я пытаюсь рекурсивно написать свой код. Пока что у меня есть что-то вроде ниже.

def multitree(node):
     tmp_list = child(node)
     for child2 in tmp_list:
           if len(child(child2)))==0:       #if you hit a leaf (dead end), go to next element
                 continue
           else:
                 multitree(child2)

Но на данный момент, я не уверен, что вернуть. По сути, я хочу отобразить все многопутевое дерево, пока не достигну листа для всего. Есть идеи или советы? Спасибо, парни.

редактировать:

Обновление 1. Для полноты картины я набросал примерное представление о том, что требуется для функции child(): https://i.imgur.com/3MkfsYc.png В основном, чтобы найти дочерние узлы узла, отмеченного стрелкой child() требуется список узлов между корнем и самим узлом, то есть узлами, помеченными красной точкой.

Обновление 2:

Я написал child (узел), как показано ниже, и в настоящее время я работаю над этим -

def pathwalk(node):

    children = child(node)
    paths = [child(node.append(kid)) for kid in children]

    return paths

Answer 1

Вы можете сделать что-то подобное, чтобы получить только самый длинный путь. Здесь он получает список узлов, откуда вы можете извлечь любую соответствующую информацию:

def longest_path(node):
    children = child(node)

    if not children: # leaf node
        return [node]

    children_vals = [longest_path(c) for c in children]
    longest = max(children_vals, key=len)
    return [node] + longest

Не обрабатывает связи, или, скорее, выбирает один вариант произвольно.

(примечание: полу-проверено)

Answer 2

Я думаю, что нашел проблему. Так как я хотел сохранить рабочий список всех узлов, которые вы нашли потомков (вы отслеживаете путь, по которому идете, смотрите imgur pic). Я отредактировал рутину Illuvatar, добавив

children_vals = [longest_path(node+[c]) for c in children]

Таким образом, вы рекурсивно объединяете каждого родителя с его дочерним элементом.