Skip to content

Instantly share code, notes, and snippets.

@sheac
Last active May 22, 2019 17:45
Show Gist options
  • Save sheac/76e50222203dedca9161c8ab22a2cd3a to your computer and use it in GitHub Desktop.
Save sheac/76e50222203dedca9161c8ab22a2cd3a to your computer and use it in GitHub Desktop.
Dependency Resolver

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment