qiime2 / provenance-lib

QIIME 2 Provenance Replay Tools
BSD 3-Clause "New" or "Revised" License
3 stars 4 forks source link

Dependency-aware node ordering for replay #33

Closed ChrisKeefe closed 2 years ago

ChrisKeefe commented 2 years ago

In order to successfully replay an analysis, we must order Actions such that all dependencies of an Action are satisfied before that Action may be run - beginning with nodes of in-degree 0, and ending with nodes of out-degree 0.

I think a topological sort will do this for us.

Topological sorts are not by definition unique, so we may get varying sort results as things change. (e.g this python version change -> sort order change). lexical_topological_sort will let us impose a more nuanced ordering, at the cost of a little bit of complexity. This commit from the same issue is the best example I've found to date of what a key function might look like.

ChrisKeefe commented 2 years ago

Questions: