sorting python list based on "dependencies" from dictionary

Question

Suppose I have the following list foo that I would like to sort:

foo = [63,64,65]

To inform the sort, I have the following dictionary of "dependencies", where if a value is in a list for a key, that value must sort higher than the key in list foo:

bar = {
    63: [64, 65],
    64: [65]
}

For example, looking at list foo, we see the value 63 at index 0. But, checking the dictionary bar, we see that 63 has "dependencies" 64 and 65, so both those values must sort higher in foo.

I'm confident I could cobble something together, but am interested in algorithms and/or other approaches to solve this sorting scenario. Thanks.

UPDATE: Many in the comments have pointed out this is likely a graphing / topological problem. Thanks for that, as this is, in fact, part of a larger task of sorting nodes in a graph.

Update: toposort was sugggested to look at, and this precisely fits the bill.

Answer 1

So, putting all the comments together:

Your situation corresponds to a directed graph, where each edge is a dependency. The right way to sort a directed (acyclical) graph, or short DAG, is called topological sorting.

In Python there is already a package that can do this, toposort. It requires, however, that your values are sets, not lists, but that is easy to fix:

from toposort import toposort_flatten

bar = {
    63: [64, 65],
    64: [65]
}

graph = dict(zip(bar.keys(), map(set, bar.values())))
sorted_graph = toposort_flatten(graph, sort=True)

Since it sound like your graph may contain entries which are not in foo, you could sort foo like this:

foo = [63,64,65]
foo_set = set(foo)
foo_sorted = [x for x in sorted_graph if x in foo_set]
print(foo_sorted)
# [65, 64, 63]

Or, if the graph is a lot larger than the list you want to sort (and iterating over it takes a lot of time), build a dictionary:

graph_sorted_lookup = {x: i for i, x in enumerate(sorted_graph)}
foo_sorted = sorted(foo, key=graph_sorted_lookup.get)