Paddy McCarthy <paddy3...@gmail.com> added the comment:
I've been playing with Python 3.9.0rc1 and was looking at a particular graph to
see when it released tasks for processing.
I ran the following code:
from functools import reduce
from pprint import pprint as pp
from collections import defaultdict
from graphlib import TopologicalSorter
from heapq import heapify, heappush, heappop, heappushpop
print("""
###
### TASK DEPENDENCY
###
A -> B -> C
↓ ↓ ↓
D -> E -> F
""")
graph3 = {"A": {"B", "D"},
"B": {"C", "E"},
"C": {"F"},
"D": {"E"},
"E": {"F"},
}
tasktime = {task: 2 for task in 'ABCDEF'}
def simulate(graph, tasktime):
print("\n## NEW SIMULATION")
t = 0
heap = []
heapify(heap)
print("\n# Task runtimes:")
for node, tm in tasktime.items():
print(f" {node}: {tm}")
print("\n# OUTPUT. (:> for task start times, <: for stop times).\n")
ts = TopologicalSorter(graph)
ts.prepare()
while ts.is_active():
for node in ts.get_ready():
finish = t + tasktime[node]
heappush(heap, (finish, node))
print(f"{' ' * t}{node}:> @{t}")
t, node = heappop(heap)
print(f"{' ' * t}{node}<: @{t}")
ts.done(node)
simulate(graph3, tasktime)
tasktime['C'] = 1
simulate(graph3, tasktime)
I got the following output:
###
### TASK DEPENDENCY
###
A -> B -> C
↓ ↓ ↓
D -> E -> F
## NEW SIMULATION
# Task runtimes:
A: 2
B: 2
C: 2
D: 2
E: 2
F: 2
# OUTPUT. (:> for task start times, <: for stop times).
F:> @0
F<: @2
C:> @2
E:> @2
C<: @4
E<: @4
B:> @4
D:> @4
B<: @6
D<: @6
A:> @6
A<: @8
## NEW SIMULATION
# Task runtimes:
A: 2
B: 2
C: 1
D: 2
E: 2
F: 2
# OUTPUT. (:> for task start times, <: for stop times).
F:> @0
F<: @2
C:> @2
E:> @2
C<: @3
E<: @4
B:> @4
D:> @4
B<: @6
D<: @6
A:> @6
A<: @8
>>>
Note that in the second simulation, C finish, but B isn't then immediately
started. I have my own code that also works like this but it isn't optimal.
Thanks guys.
----------
nosy: +Paddy McCarthy
_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue17005>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
