Algorithm for converting hierarchical flat data (w / ParentID) to a sorted flat list with indentation levels

Question

I have the following structure:

MyClass { guid ID guid ParentID string Name } 

I would like to create an array that contains the elements in the order in which they should be displayed in the hierarchy (for example, according to their "left" values), as well as a hash that displays a pointer to the indent level.

For instance:

 ID Name ParentID ------------------------ 1 Cats 2 2 Animal NULL 3 Tiger 1 4 Book NULL 5 Airplane NULL 

This will create the following objects:

 // Array is an array of all the elements sorted by the way you would see them in a fully expanded tree Array[0] = "Airplane" Array[1] = "Animal" Array[2] = "Cats" Array[3] = "Tiger" Array[4] = "Book" // IndentationLevel is a hash of GUIDs to IndentationLevels. IndentationLevel["1"] = 1 IndentationLevel["2"] = 0 IndentationLevel["3"] = 2 IndentationLevel["4"] = 0 IndentationLevel["5"] = 0 

For clarity, it looks like this:

 Airplane Animal Cats Tiger Book 

I would like to iterate over the items the least number of times. I also do not want to create a hierarchical data structure. I would prefer to use arrays, hashes, stacks or queues.

Two goals:

• Keep the identifier hash at the indent level.
• Sort a list that contains all objects according to their left values.

When I get a list of elements, they do not have a special order. Siblings must be ordered by the Name property.

Update: It may seem like I haven’t tried to come up with a solution myself and just want others to do the work for me. However, I tried to come up with three different solutions, and I was stuck on each. One reason may be that I was trying to avoid recursion (possibly by mistake). I do not send partial solutions that I still have, because they are incorrect and can adversely affect the decisions of others.

Answer 1

The Wonsungi post helped a lot, however this is for the general schedule, not for the tree. So I changed it a bit to create an algorithm designed specifically for the tree:

 // Data strcutures: nodeChildren: Dictionary['nodeID'] = List<Children>; indentLevel: Dictionary['nodeID'] = Integer; roots: Array of nodes; sorted: Array of nodes; nodes: all nodes // Step #1: Prepare the data structures for building the tree for each node in nodes if node.parentID == NULL roots.Append(node); indentLevel[node] = 0; else nodeChildren[node.parentID].append(node); // Step #2: Add elements to the sorted list roots.SortByABC(); while roots.IsNotEmpty() root = roots.Remove(0); rootIndentLevel = indentLevel[root]; sorted.Append(root); children = nodeChildren[root]; children.SortByABC(); for each child in children (loop backwards) indentLevel[child] = rootIndentLevel + 1 roots.Prepend(child) 

Answer 2

I needed a similar algorithm for sorting tasks with dependencies (each task could have a parent task, which was to be performed in the first place). I found topological sorting . The following is an iterative implementation in Python with very detailed comments.

The indent level can be calculated by performing topological sorting. Just set the indentation level <node to the parent node indentation level + 1, as it is added to the topological order.

Note that there are many valid topological orders. To ensure that the parent nodes of the topological ordering form child nodes, select a topological sorting algorithm based on the first passage through the depth of the graph created by the partial ordering information.

Wikipedia provides two more algorithms for topological sorting . Please note that these algorithms are not so good, because the first is a traversal of the width, and the second is recursive.

Answer 3

For hierarchical structures, you will almost certainly need recursion (if you allow arbitrary depth). I quickly cracked some ruby ​​code to illustrate how you could achieve this ( although I did not indent ):

 # 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 

If you do not say ruby, I can remake it in something else.

Edit: I updated the code above to output both data structures.

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}