Как использовать этот код поиска в глубину для получения топологической сортировки?

Проблема: мне нужно реализовать топологический поиск, используя следующий код поиска в глубину.

Примечание. Исходный код взят из здесь, и это задача, приведенная в конце главы.

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

Обратите внимание, что хотя в некоторых решениях используется стек, в этом коде явно не указано использование стека. Скорее, стек подразумевается в рекурсивном вызове dfsvisit.

from pythonds.graphs import Graph
# Definitions
# discovery time == iterations it took for the program to find the vertex and turn it gray
# finish time == iterations it took for the program to turn the vertex black
# pred == predecessor indicator

class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0                       # self has an attribute 'time' (counter) that initiates at 0

    def dfs(self):
        for aVertex in self:            
            aVertex.setColor('white')
            aVertex.setPred(-1)
        for aVertex in self:
            if aVertex.getColor() == 'white':
                self.dfsvisit(aVertex)

    def print_graph(self):
        for key in sorted(list(self.vertices.keys())):
            print(key + str(self.vertices[key].neighbors + " " + str(self.vertices[key].dis)))


    def dfsvisit(self,startVertex):                     # Initiate the visit vunction of the current object (self) at the starting vertex (startVertex)
        finish_times = []                                       # Instantiate the a list to keep finish times for each node
        startVertex.setColor('gray')                    # Set the color of the starting vertex to 'gray' (discovered)
        self.time += 1                                  # Increment the timer
        startVertex.setDiscovery(self.time)             # Assign the discovery time to the current vertex (startVertex)
        for nextVertex in startVertex.getConnections(): # Begin cycling through the connected vertices (nextVertex) of startVertex
            if nextVertex.getColor() == 'white':        # If a vertex (nextVertex) with the attribute color of white is found, then do the following:
                nextVertex.setPred(startVertex)         # Set the predecessor indicator of the next vertex as the current vertex (ie if B is white and connected to A, set B's predecessor as A)
                self.dfsvisit(nextVertex)               # Recursively calls itself with the next vertex until the color of the next vertex is no longer white (i.e. all have been explored)
        startVertex.setColor('black')                   # Set the current vertice's color to black (explored)
        self.time += 1                                  # Increment the timec counter
        startVertex.setFinish(self.time)                # Assign the finish time to the current vertex (startVertex)
        finish_time = [startVertex, startVertex.setFinish(self.time)]  # append vertex and finish times to finish_time list
       return finish_time                                             # return the finish_time list

Извините за мои длинные комментарии. Надеясь понять, как реализовать топологический поиск внутри этого кода.


person alofgran    schedule 31.08.2019    source источник
comment
Непонятно, какую помощь вы хотите. Topological sorting является побочным эффектом Depth-first search. Вам не нужно ничего специально реализовывать для достижения сортировки или реальной сортировки. Данные сортируются в момент их вставки в график. Код, который вы показали, реализует подход обхода, когда посещенные узлы помечаются, а не сохраняются в стеке. Взгляните на сравнение.   -  person cassandrad    schedule 02.09.2019
comment
@cassandrad - спасибо за ответ. Я понимаю, что топологическая сортировка является потенциальным результатом поиска в глубину, но помимо того, что я перечислил, требуется дополнительный код. Поэтому я ищу помощь в написании этого кода в приведенном выше коде DFS, а затем в распечатке заказа. Я не делал этого раньше в классе и еще не нашел ресурса, полезного для этого конкретного случая.   -  person alofgran    schedule 02.09.2019
comment
Как я упоминал в своем отчете, стек в приведенном выше коде неявный. Нельзя ли реализовать топологический поиск через этот неявный стек (вместо явного, который вы предлагаете)? Ссылка, которую я предложил выше, содержит документацию, которая, кажется, гарантирует, что это возможно.   -  person alofgran    schedule 02.09.2019
comment
Похоже, что рекурсивная версия псевдокода в статье Википедии, на которую вы ссылаетесь, также использует неявный стек. Поправьте меня, если я ошибаюсь.   -  person alofgran    schedule 02.09.2019
comment
Я не знаю, что такое Graph API, который вы расширяете, поэтому я не могу напрямую помочь вам с вашим кодом. Но я написал предыдущий ответ о том, как можно преобразовать поиск в глубину в топологическую сортировку, что может быть актуально здесь.   -  person Blckknght    schedule 03.09.2019
comment
@onhamae, вы правы: верхняя сортировка может быть реализована с явным и неявным стеком. Итак, что вы хотите, так это помочь вам переписать свой код для явного использования стека?   -  person cassandrad    schedule 03.09.2019
comment
@cassandrad - точно. У меня есть неявный стек в моей рекурсивной DFS, но я еще не смог понять, как превратить его в топологический поиск.   -  person alofgran    schedule 04.09.2019
comment
@Blckknght - я думаю, что конец ответа, на который вы ссылаетесь, особенно уместен (рекурсивная функция). Сейчас работаем над его реализацией. Я обновлю это, если добьюсь успеха.   -  person alofgran    schedule 05.09.2019