deeppavlov/models/spelling_correction/levenshtein/tabled_trie.py
def generate_postorder(self, trie):
        """
        Обратная топологическая сортировка
        """
        order, stack = [], []
        stack.append(trie.root)
        colors = ['white'] * len(trie)
        while len(stack) > 0:
            index = stack[-1]
            color = colors[index]
            if color == 'white': # вершина ещё не обрабатывалась
                colors[index] = 'grey'
                for child in trie._get_children(index):
                    # проверяем, посещали ли мы ребёнка раньше
                    if child != Trie.NO_NODE and colors[child] == 'white':
                        stack.append(child)
            else:
                if color == 'grey':
                    colors[index] = 'black'
                    order.append(index)
                stack = stack[:-1]
        return order
def generate_postorder(self, trie):
        """
        Обратная топологическая сортировка
        """
        order, stack = [], []
        stack.append(trie.root)
        colors = ['white'] * len(trie)
        while len(stack) > 0:
            index = stack[-1]
            color = colors[index]
            if color == 'white': # вершина ещё не обрабатывалась
                colors[index] = 'grey'
                for child in trie._get_children(index):
                    # проверяем, посещали ли мы ребёнка раньше
                    if child != Trie.NO_NODE and colors[child] == 'white':
                        stack.append(child)
            else:
                if color == 'grey':
                    colors[index] = 'black'
                    order.append(index)
                stack = stack[:-1]
        return order
def generate_postorder ( self , trie ) : order , stack = [ ] , [ ] stack . append ( trie . root ) colors = [ 'white' ] * len ( trie ) while len ( stack ) > 0 : index = stack [ - 1 ] color = colors [ index ] if color == 'white' : # вершина ещё не обрабатывалась colors [ index ] = 'grey' for child in trie . _get_children ( index ) : # проверяем, посещали ли мы ребёнка раньше if child != Trie . NO_NODE and colors [ child ] == 'white' : stack . append ( child ) else : if color == 'grey' : colors [ index ] = 'black' order . append ( index ) stack = stack [ : - 1 ] return order
Обратная топологическая сортировка
Обратная топологическая сортировка