Dependency Resolver

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.

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, 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:

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.