Given a hash representing a dependency DAG, with job names and jobs they are dependent on, create a list of job names ordered such that when you iterate over them you are guaranteed to have already visited all the dependencies by the time you inspect a given item. Not particularly efficient, but it shouldn't be a problem for our use case of a fe…

job_ordering.py

jobs = {
    "F": ["E"],
    "A": [],
    "B": ["A"],
    "C": ["A"],
    "D": ["B", "C"],
    "G": ["A", "D"],
    "E": []
}
 
ordered_jobs = []
ordered_jobs_set = set()
 
while len(ordered_jobs) < len(jobs.keys()):
    for job, deps in jobs.iteritems():
        if job in ordered_jobs_set:
            continue
        if not set(deps).issubset(ordered_jobs_set):
            continue
        ordered_jobs.append(job)
        ordered_jobs_set = set(ordered_jobs)

print ordered_jobs
 
# Tests
seen = set()
for job in ordered_jobs:
    dependent_on = jobs[job]
    seen.update(job)
    print dependent_on, seen
    assert(set(dependent_on).issubset(seen))