Page MenuHomeSoftware Heritage
Paste P142

topo_sort
ActivePublic
Actions

Authored by olasd on Mar 7 2017, 4:28 PM.
def topo_sort(revisions):
"""revisions: dict id -> parents"""
done = set()
remaining = set(revisions)
set_revisions = {
rev: (set(parents), parents)
for rev, parents in revisions.items()
}
while remaining:
for rev in remaining.copy():
set_parents, parents = set_revisions[rev]
if set_parents <= done:
yield (rev, parents)
done.add(rev)
remaining.remove(rev)
About · Developer information · Legal