a-b-c-f.png

a-b-c.png

dependency-resolver.md

Dependency Resolver

We are going to design an algorithm for resolving module/package dependencies for a compiler.

Data structures

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]
}

Problem

Our goal is to create a function that orders the dependencies for building.

Input

Your function will be given a list of Dependency objects in no particular order.

Output

Your function will return a list of Dependency objects in a very specific order: The order is such that for any item in the list, it depends (maybe transitively) only on later items in the list. Or: It won't be possible to follow dependency arrows to items earlier in the list.

For example, with our example A, B & C above (a-b-c.png) two valid orderings are:

1. A, B, C
2. 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.

Bonus

How would we modify the algorithm to accomodate a dependency tree that is too large to fit on a single machine, or in a low-computational-resources environment where the device doesn't have enough space to fit a regular-sized tree?