(An Untitled Masterwork)
ActivePublic
Actions

Authored by seirl on Mar 15 2017, 3:28 PM.

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)

(An Untitled Masterwork)ActivePublicActions