Page Menu
Home
Software Heritage
Search
Configure Global Search
Log In
Paste
P142
topo_sort
Active
Public
Actions
Authored by
olasd
on Mar 7 2017, 4:28 PM.
Edit Paste
Archive Paste
View Raw File
Subscribe
Mute Notifications
Award Token
Flag For Later
Tags
None
Subscribers
None
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
)
Event Timeline
olasd
created this paste.
Mar 7 2017, 4:28 PM
2017-03-07 16:28:18 (UTC+1)
olasd
edited the content of this paste.
(Show Details)
Mar 15 2017, 3:05 PM
2017-03-15 15:05:37 (UTC+1)
Log In to Comment