0
$\begingroup$

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 "placed" and "unplaced" items (the former is empty at the beginning, and the latter initialized with a copy of the unsorted list), and then greedily moving "unplaced" items to the "placed" list when they do not have any ancestors in the "unplaced" list (until the "unplaced" list is empty). That being said... I am curious whether there is a more efficient way to achieve these results. Thanks in advance!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.