We are going to design an algorithm for resolving module/package dependencies for a compiler.
A Dependency is an object with:
- an id
- a list of references to downstream Dependencies
For the example graphs above, we have:
// E
e = {
id: "e",
deps: []
}
// D
d = {
id: "d",
deps: [&e]
}
// C
c = {
id: "c",
deps: [&d]
}
// B:
b = {
id: "b",
deps: [&d]
}
// A:
a = {
id: "a",
deps: [&b, &c]
}
// F:
f = {
id: "f",
deps: [&c]
}
///////
// C
c = {
id: "c",
deps: []
}
// B:
b = {
id: "b",
deps: []
}
// A:
a = {
id: "a",
deps: [&b, &c]
}
Our goal is to create a function that orders the dependencies.
Your function will be given a list of Dependency objects in no particular order.
Your function will return a list of Dependency objects in a very specific order: The order is such that for any item, it depends only on later items in the list. It will never depend on items earlier in the list.
For example, with our example A, B & C above (a-b-c.png
) two valid orderings are:
- A, B, C
- A, C, B
Consider a more complicated example: a-b-c-f.png
Valid orderings include:
- A, F, B, C, D, E
- F, A, C, B, D, E
Note that both A and F depend on C. Therefore C must come after both A and F in the ordering. Also, A depends on both B and C. So B and C must both come after A.