Page Menu
Home
Software Heritage
Search
Configure Global Search
Log In
Paste
P147
(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:54 (UTC+1)
Log In to Comment