Problem statement: Find out the order in which projects should be build such that dependencies are built first. Dependencies are represented using a list of pairs of projects, where the second project is dependent on the first project. See test case for details.
My attempt: Initialization of dependency based dictionaries take O(E) time. Initialization of buildOrder array takes O(P) time. Where P is number of projects and E is number of edges/dependencies.
Does the while loop take O(E) time?
I assume that for loop inside while loop will run in total once for each edge. In other words, you can also say that outer while loops runs P times and inner for loop runs E/P times on average. So, time complexity of while loop is O(P*E/P) = O(E). Is this statement correct?
Thus, beyond initialization, it only takes O(E) to solve the problem.
from collections import defaultdict
class NoValidBuildOrderError(Exception):
pass
def determine_build_order(projects, dependencies):
parentMap = defaultdict(set)
childrenMap = defaultdict(set)
for d, p in dependencies:
parentMap[p].add(d)
childrenMap[d].add(p)
pointer = 0
buildOrder = [p for p in projects if not parentMap[p]]
while len(buildOrder) < len(projects):
try:
currentProject = buildOrder[pointer]
except IndexError:
raise NoValidBuildOrderError()
for child in list(childrenMap[currentProject]):
parentMap[child].remove(currentProject)
if not parentMap[child]:
buildOrder.append(child)
pointer += 1
return buildOrder
def test_determine_build_order():
projects = ["a", "b", "c", "d", "e", "f", "g"]
dependencies = [
("d", "g"),
("a", "e"),
("b", "e"),
("c", "a"),
("f", "a"),
("b", "a"),
("f", "c"),
("f", "b"),
]
build_order = determine_build_order(projects, dependencies)
print(build_order)
for dependency, project in dependencies:
assert build_order.index(dependency) < build_order.index(project)
def test_impossible_build_order():
projects = ["a", "b"]
dependencies = [("a", "b"), ("b", "a")]
try:
determine_build_order(projects, dependencies)
except NoValidBuildOrderError:
return # Expected error, test passes
raise AssertionError("Expected NoValidBuildOrderError, but it wasn't raised.")
def run_tests():
test_determine_build_order()
test_impossible_build_order()
print("All tests passed!")
if __name__ == "__main__":
run_tests()
