Алгоритм для преобразования иерархических плоских данных (w/ParentID) в отсортированный плоский список w/уровни отступа

Для иерархических структур вам почти наверняка понадобится рекурсия (если вы допускаете произвольную глубину). Я быстро набросал немного кода на руби, чтобы проиллюстрировать, как вы можете достичь этого (хотя я не сделал отступы):

# setup the data structure
class S < Struct.new(:id, :name, :parent_id);end

class HierarchySorter

    def initialize(il)
        @initial_list = il
        first_level = @initial_list.select{|a| a.parent_id == nil}.sort_by{|a| a.name }
        @final_array = subsort(first_level, 0)
    end

    #recursive function
    def subsort(list, indent_level)
        result = []
        list.each do |item|
            result << [item, indent_level]
            result += subsort(@initial_list.select{|a| a.parent_id == item.id}.sort_by{|a| a.name }, indent_level + 1)
        end
        result
    end

    def sorted_array
        @final_array.map &:first
    end

    def indent_hash
        # magick to transform array of structs into hash
        Hash[*@final_array.map{|a| [a.first.id, a.last]}.flatten]
    end

end

hs = HierarchySorter.new [S.new(1, "Cats", 2), S.new(2, "Animal", nil), S.new(3, "Tiger", 1), S.new(4, "Book", nil),
    S.new(5, "Airplane", nil)]

puts "Array:"
puts hs.sorted_array.inspect

puts "\nIndentation hash:"
puts hs.indent_hash.inspect

Если вы не знаете руби, я могу переделать его на что-нибудь другое.

Edit: Я обновил код выше, чтобы вывести обе структуры данных.

Outputs:

Array:
[#<struct S id=5, name="Airplane", parent_id=nil>, #<struct S id=2, name="Animal", parent_id=nil>, #<struct S id=1, name="Cats", parent_id=2>, #<struct S id=3, name="Tiger", parent_id=1>, #<struct S id=4, name="Book", parent_id=nil>]

Indentation hash:
{5=>0, 1=>1, 2=>0, 3=>2, 4=>0}

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

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

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

Википедия дает еще два алгоритма топологической сортировки . Обратите внимание, что эти алгоритмы не так хороши, потому что первый - обход в ширину, а второй - рекурсивный.