Как перечислить все пути в структуре направленного ациклического графа с помощью Python, когда структуру данных можно обнаружить только путем обхода?

avatar
danieltalsky
8 августа 2021 в 20:35
305
2
0

Пожалуйста, позвольте мне уточнить некоторые детали, прежде чем начать:

  1. Я очень много работал, чтобы исследовать эту проблему самостоятельно. Я рассмотрел такие решения, как это или это, но все эти решения предполагают, что у вас есть вся структура данных в памяти.
  2. Это для чего-то практического, и не домашнее задание или вопрос собеседования. Я пытался найти решение, но не смог, хотя знаю, что это теоретически возможно.
  3. Специфика: я использую python/Selenium для обхода файла Twine, но я показываю интерфейс обобщенного псевдокода, потому что эти детали не важны для решения проблемы, только чтобы продемонстрировать, что я нужно пройти путь, чтобы обнаружить его.

Итак, у меня есть направленный ациклический граф, содержащий около 150 узлов. Существует один начальный узел и множество конечных узлов.

Представьте, что у меня есть похожий интерфейс для обхода графа:

class TheGraphToTraverse:

    def get_the_first_node(self):
        pass

    def get_the_list_of_edges_from_the_current_node(self):
        """
        Returns list of links/edges that can be followed
        """

    def follow_this_edge(self, edge):
        """
        Follow an edge link to its destination node
        """

    def go_back_one_step(self):
        """
        Navigate back one step
        """

    def go_back_to_the_start_node(self):
        """
        Start over from the beginning node
        """

    def is_this_node_an_end_node(self):
        """
        Is the current node an end node with no further edges to traverse?
        """

Как мне адаптировать (рекурсивный или нерекурсивный) алгоритм, подобный этим, но без необходимости передавать сам график в рекурсивную функцию:

data = {1 : [2,3],   # Directed acyclic graph adjacency list
        2 : [3],
        3 : [4,5],
        4 : [5]}

def dfs(data, path, paths = []):   
    datum = path[-1]              
    if datum in data:
        for val in data[datum]:
            new_path = path + [val]
            paths = dfs(data, new_path, paths)
    else:
        paths += [path]
    return paths

Видите, как этот алгоритм (и все, что я могу найти в Интернете) передает всю структуру данных? У меня нет графа в виде структуры данных, и мне нужно обнаружить его во время обхода, поэтому мне нужно иметь возможность сохранять какое-то состояние на моем текущем пути, и у меня возникают проблемы с четким пониманием того, как надежно сохранить это состояние. .

Я зашел так далеко:

    list_of_all_paths = []
    g = TheGraphToTraverse()
    first_node = g.get_the_first_node()
    list_of_all_paths = dfs(g, first_node, list_of_all_paths)

    def dfs(g: TheGraphToTraverse, path, all_paths):

        # check for end state
        if g.is_this_node_an_end_node:
            all_paths += [path]
            g.go_back_one_step()
            # I recognize I'm not sure how to store 
            # the previous edges I've stored for this path
            all_paths = dfs(g, path, all_paths)
        else:
            edges = g.get_the_list_of_edges_from_the_current_node()
            # how do I know which of these I've already tried?
            # how do I know if this is a list of 
            # edges I've already tried?
            for edge in edges:
                g.follow_this_edge(edge)
                all_paths = dfs(g, path, all_paths)
        return all_paths

Любой вспомогательный или адаптированный алгоритм, даже если он не на Python или не является рекурсивным, подойдет. Большое спасибо за участие в этом.

Источник
Jasmijn
8 августа 2021 в 20:46
0

Есть ли конкретная причина, по которой вы сначала не строите график?

Karl Knechtel
8 августа 2021 в 21:05
0

Я не понимаю. Почему в вашем классе Graph есть понятие «текущий» узел?

Karl Knechtel
8 августа 2021 в 21:18
0

Почему вы должны спрашивать граф, каковы ребра этого узла, а не спрашивать любой произвольный узел, каковы его исходящие ребра? Даже если эта информация вычисляется на лету, это должно быть возможно из экземпляра узла — почему бы и нет?

danieltalsky
8 августа 2021 в 21:20
0

Привет, @KarlKnechtel, как я уже сказал выше, я тестирую странную структуру HTML/JavaScript, по которой я перемещаюсь через селен, фактически нажимая на ссылки, а затем выполняя оператор поиска XPath, чтобы увидеть, какие ссылки/ребра находятся на текущий узел. Пока я на самом деле не перешел к узлу, я не могу видеть, что там.

Karl Knechtel
8 августа 2021 в 21:27
0

Хорошо, но почему это вызывает проблему? Перейдя к узлу, вы можете вычислить ребра этого узла, изучив узел, верно? И вам не нужно полагаться на какой-то другой интерфейс Graph, "запомнивший" "текущий" узел, потому что вы уже находитесь там и имеете этот экземпляр. Так что на самом деле все, что вам нужно сделать, это заменить поиск data[datum] кодом, который фактически дает вам узлы-преемники из datum.

danieltalsky
8 августа 2021 в 21:29
0

Я предполагаю, что мое имя класса псевдокода не совсем точное. Возможно, мне следовало назвать его GraphNodeTraverser? В основном я пытался объяснить, что мне действительно нужно вернуться назад и вперед, чтобы увидеть, какие узлы доступны.

Karl Knechtel
8 августа 2021 в 21:31
0

Конечно, но дело в том, что попытка поместить эту логику в отдельный класс — и заставить его «отслеживать» «текущий» узел — без необходимости усложняет проблему. Весь смысл написания рекурсивного алгоритма для структуры графа заключается в том, что вы всегда знаете, что такое «текущий узел», без какой-либо необходимости в интерфейсе для «следования этому ребру» (это происходит автоматически, когда вы делаете рекурсивный вызов) или « вернуться на один шаг назад" (это происходит автоматически при возврате рекурсивного вызова).

danieltalsky
8 августа 2021 в 21:33
0

Да, но в данном случае это своего рода веб-приложение в стиле «Выбери себе приключение». Если вы дошли до конца пути, вы не можете просто полагаться на рекурсию для восстановления веб-страницы до ее предыдущего состояния. На самом деле вам нужно НАЖАТЬ кнопку «Назад», чтобы вернуться к предыдущему узлу.

Ответы (2)

avatar
Jasmijn
8 августа 2021 в 21:01
1

В настоящее время вы не предоставляете метод для получения любого узла, кроме первого узла, поэтому я предполагаю, что вы ищете только ребра?

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

def dfs(g: TheGraphToTraverse, current_path=()):
    '''Depth first search on an unbuilt graph. ``current_path`` is a tuple of edges, forming a single traversal path.

    Returns an iterator of tuples of edges.
    '''
    if g.is_this_node_an_end_node():
        yield current_path
    else:
        edges = g.get_the_list_of_edges_from_the_current_node()
        for edge in edges:
            # A "sandwich" of graph traversal management with the recursion in between.
            # This ensures that every follow_this_edge is paired with a go_back_one_step.
            g.follow_this_edge(edge)
            yield from dfs(g, current_path + (edge,))
            g.go_back_one_step()

g = TheGraphToTraverse()
list_of_all_paths = list(dfs(g))  # type: list[tuple[edge_type, ...]]
danieltalsky
8 августа 2021 в 21:26
0

Я честно ошеломлен тем, что ответ такой простой (и довольно питонический). Я не был знаком с yield from и должен был прочитать об этом. Пожалуйста, позвольте мне попробовать реализовать это, прежде чем принять ответ, но я обязательно это сделаю.

danieltalsky
8 августа 2021 в 21:34
1

Кроме того, просто... большое спасибо. Я задавал этот вопрос в разных местах, в том числе несколько здесь, на SO, медленно уточняя его, чтобы донести идею, и вы явно ближе всего к какой-либо реальной помощи, поэтому я полон благодарности.

avatar
Karl Knechtel
8 августа 2021 в 21:50
1

Основываясь на вашем описании проблемы и обсуждении комментариев, я вполне уверен, что вам нужны только следующие абстракции:

def get_edges_from(node):
    # examine the current node to determine where we can go.
    # returns a list of graph edges to follow.
    # If the logic for following an edge requires the current node,
    # then include that information in the 'edge' representation.

def get_node(edge):
    # follow an edge and return the node at the other end.

Давайте еще раз посмотрим на исходный код:

def dfs(data, path, paths = []):   
    datum = path[-1]              
    if datum in data:
        for val in data[datum]:
            new_path = path + [val]
            paths = dfs(data, new_path, paths)
    else:
        paths += [path]
    return paths

Здесь data представляет собой представление графа, которое позволяет легко искать узлы-преемники напрямую: data[datum]. datum — это «текущий» узел в нашей рекурсии (нам не нужны какие-либо инструменты для внешнего отслеживания, потому что это подразумевается в процессе рекурсии; и нам не нужен способ «вернуться назад», потому что рекурсивные дескрипторы это тоже). Мы абстрагировали этот процесс в глобальные функции, которые работают с узлом, поэтому нам не нужно его передавать. Вместо этого мы просто заменяем поиск.

Отдельно нам не нужен специальный способ сказать нам, является ли узел листом; мы просто проверяем, действительно ли мы рекурсировали оттуда. Существующий код проверяет if datum in data:, чтобы сделать это (что могло бы вызвать ошибку, если бы структура содержала пустой список для узлов-последователей). Вместо этого мы будем использовать логику флагов локально.

Наконец, я хочу очистить логику, которая return соответствует значению paths, потому что оно уже изменено для сохранения общего результата. Я также удалил значение по умолчанию, поскольку изменяемые значения по умолчанию плохие.

Применение этих изменений вместе с некоторыми косметическими изменениями имени дает:

def dfs(path, paths):   
    current_node = path[-1]
    is_leaf = True
    for edge in get_edges_from(current_node):
        new_path = path + [get_node(edge)]
        dfs(data, new_path, paths)
        is_leaf = False
    if is_leaf:
        paths.append(path)

Затем мы можем добавить помощника для запуска рекурсии:

def dfs_from(root):
    paths = []
    dfs([root], paths) # populates the `paths` list
    return paths

Конечно, это можно улучшить. Текущий алгоритм не кэширует результаты соединений: то есть, если есть несколько способов добраться до узла в середине графа, алгоритм будет повторять обход каждого пути вперед от этого узла для каждого пути, ведущего к узлу. Это. Если бы я начинал с нуля, я бы также определенно использовал подход рекурсивного генератора, а не создавал список, передаваемый в рекурсии. Я просто хотел показать, как мало изменений требуется на самом деле.

Karl Knechtel
8 августа 2021 в 21:58
1

С другой стороны, подход с рекурсивным генератором может затруднить реализацию оптимизации, на которую я намекал. Вы не могли бы просто functools.lru_cache результатов, например, потому что в кеше будут храниться объекты-генераторы, которые исчерпываются при первом повторении.

danieltalsky
8 августа 2021 в 23:52
0

Вы видели подход Jasmijn, основанный на генераторе?

danieltalsky
9 августа 2021 в 02:03
0

Кроме того, большое спасибо за то, что нашли время, чтобы объяснить, что мне не хватало. Я очень ценю это.