How to (Efficiently) Sort a List of Items with Parent/Child Relationship I have a list of items that have a parent/child/grandchild/etc. type of relationship. Each item has a list of descendants, and an _.isDescendentOf(other) member function that returns true when a node is a descendant of another node (they have a list of immediate parents, and can sweep upwards to find grandparents). Some of the items may not have a relationship with one another. I need to sort these items such that no item comes before an item it is a descendant of.
Consider items of the format (a, [b, c]) which indicates that a has descendants b and c. If we had the unsorted list (with an invalid ordering): [(c, []), (a, [b, c]), (b, [c]), (d, [])]
Valid orderings would be: [(a, [b, c]), (b, [c]), (c, []), (d, [])] or [(d, []), (a, [b, c]), (b, [c]), (c, [])]
(Note, (d, []) can technically be placed anywhere since it does not have a relationship with the others.)
(Note, a, b, etc. are randomly-assigned placeholder names and, though they are alphabetically ordered here, in reality they are random.)
I am quite unsure how to achieve this in an efficient way. My (current) solution involves maintaining a list of &quot;placed&quot; and &quot;unplaced&quot; items (the former is empty at the beginning, and the latter initialized with a copy of the unsorted list), and then greedily moving &quot;unplaced&quot; items to the &quot;placed&quot; list when they do not have any ancestors in the &quot;unplaced&quot; list (until the &quot;unplaced&quot; list is empty). That being said... I am curious whether there is a more efficient way to achieve these results. Thanks in advance!
I think you already have implemented some sort of adjacency list representation of a directed graph. You can use a topological sorting (https://en.m.wikipedia.org/wiki/Topological_sorting) to order the items.