Page Menu
Home
Software Heritage
Search
Configure Global Search
Log In
Paste
P146
(An Untitled Masterwork)
Active
Public
Actions
Authored by
seirl
on Mar 15 2017, 3:28 PM.
Edit Paste
Archive Paste
View Raw File
Subscribe
Mute Notifications
Award Token
Flag For Later
Tags
None
Subscribers
None
def _toposort(self, rev_by_id):
children = collections.defaultdict(list)
in_degree = collections.defaultdict(int)
for rev_id, rev in rev_by_id.items():
for parent in rev['parents']:
in_degree[rev_id] += 1
children[parent].append(rev_id)
queue = collections.deque()
for rev_id in rev_by_id.keys():
if in_degree[rev_id] == 0:
queue.append(rev_id)
while queue:
rev_id = queue.popleft()
yield rev_by_id[rev_id]
for child in children[rev_id]:
in_degree[child] -= 1
if in_degree[child] == 0:
queue.append(child)
Event Timeline
seirl
created this paste.
Mar 15 2017, 3:28 PM
2017-03-15 15:28:45 (UTC+1)
Log In to Comment