Build Order

You are given a list of projects and a list of dependencies (which is a list of pairs of projects, where the second project is dependent on the first project). All of a project’s dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.

For example, the following input:

projects: a, b, c, d, e, f
dependencies: (a,d), (f,b), (b,d), (f,a), (d,c)

would produce the following output:

f, e, a, b, d, c

Solution

Using the dependencies, we can build a directed graph. The nodes at the top of the graph will be the packages which must be built first, since they have no dependencies on other packages. If we reverse the direction of this graph, the nodes at the bottom of the graph will be the packages which must be built first.

Let’s take the inputs, projects and dependencies, and build an adjacency list to represent the graph. We will reverse the direction of the dependencies in the graph - so the parent nodes will be dependent on the children.

def build_graph(projects, dependencies):
  graph = {x:set() for x in projects}

  for dependency in dependencies:
    graph[dependency[1]].add(dependency[0])

  return graph

Now, we want to identify the projects in the graph which do not have any children (as these projects have no dependencies).

def non_dependent_projects(graph):
  projects = set()

  for project in graph:
    if(len(graph[project]) == 0):
      projects.add(project)

  return projects

Once we have identified non-dependent projects, we want to remove them from the graph.

def remove_dependencies(projects, graph):
  for project in graph:
    intersect = projects.intersection(graph[project])
    graph[project] = graph[project] - intersect

  return graph

Finally, we are ready to build our general algorithm to compute the build order.

def build_order(projects, dependencies):
  graph = build_graph(projects, dependencies)
  order = []

  while(len(order) < len(projects)):
    ready_projects = non_dependent_projects(graph)

    if(len(ready_projects) == 0):
      return None
    else:
      order.extend(ready_projects)

    graph = remove_dependencies(ready_projects, graph)

    for project in ready_projects:
      graph.pop(project)

  return order