Author Paddy McCarthy
Recipients Jim Fasarakis-Hilliard, Paddy McCarthy, Zahari.Dim, belopolsky, christian.heimes, eric.smith, gaborjbernat, gdr@garethrees.org, lukasz.langa, maresb, martin.panter, miss-islington, orsenthil, pablogsal, remi.lapeyre, rhettinger, terry.reedy, tim.peters, tshepang, vstinner, wim.glenn
Date 2020-08-27.02:01:54
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1598493715.04.0.06462575371.issue17005@roundup.psfhosted.org>
In-reply-to
Content
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.
History
Date User Action Args
2020-08-27 02:01:55Paddy McCarthysetrecipients: + Paddy McCarthy, tim.peters, rhettinger, terry.reedy, belopolsky, orsenthil, vstinner, eric.smith, christian.heimes, lukasz.langa, tshepang, gdr@garethrees.org, martin.panter, wim.glenn, Zahari.Dim, Jim Fasarakis-Hilliard, pablogsal, miss-islington, remi.lapeyre, gaborjbernat, maresb
2020-08-27 02:01:55Paddy McCarthysetmessageid: <1598493715.04.0.06462575371.issue17005@roundup.psfhosted.org>
2020-08-27 02:01:55Paddy McCarthylinkissue17005 messages
2020-08-27 02:01:54Paddy McCarthycreate