Topological graph sort

Graph is a list which for each node contains a vector of child nodes in the returned list, parents appear before their children.

topological_sort(graph)

Arguments

graph

(named list) list with node vector elements mapping from child to its parents (upstream dependencies)

Value

vector listing parents before children

Details

Implementation of Kahn algorithm with a modification to maintain the order of input elements.

Examples

staged.dependencies:::topological_sort(list(A = c(), B = c("A"), C = c("B"), D = c("A")))
#> [1] "A" "B" "C" "D"
staged.dependencies:::topological_sort(list(D = c("A"), A = c(), B = c("A"), C = c("B")))
#> [1] "A" "D" "B" "C"
staged.dependencies:::topological_sort(list(D = c("A"), B = c("A"), C = c("B"), A = c()))
#> [1] "A" "D" "B" "C"
if (FALSE) {
# cycle
topological_sort(list(A = c("B"), B = c("C", "A"), C = c()))
}