python
# Let's compute CPM for given activities.
activities = {
    "A": {"dur": 1, "pred": []},
    "B": {"dur": 4, "pred": ["A"]},
    "C": {"dur": 3, "pred": ["A"]},
    "D": {"dur": 7, "pred": ["A"]},
    "E": {"dur": 6, "pred": ["B"]},
    "F": {"dur": 2, "pred": ["C", "D"]},
    "G": {"dur": 7, "pred": ["E", "F"]},
    "H": {"dur": 9, "pred": ["D"]},
    "I": {"dur": 4, "pred": ["G", "H"]},
}
# compute ES, EF via forward pass
ES = {}
EF = {}
# Topological order
# naive approach: iterate until all assigned
remaining = set(activities.keys())
while remaining:
    for act in list(remaining):
        preds = activities[act]["pred"]
        if all(p in EF for p in preds):
            ES[act] = max([EF[p] for p in preds], default=0)
            EF[act] = ES[act] + activities[act]["dur"]
            remaining.remove(act)
            
ES, EF, EF["I"]

({'A': 0, 'D': 1, 'B': 1, 'E': 5, 'H': 8, 'C': 1, 'F': 8, 'G': 11, 'I': 18},
 {'A': 1, 'D': 8, 'B': 5, 'E': 11, 'H': 17, 'C': 4, 'F': 10, 'G': 18, 'I': 22},
 22)

python
# Build successor mapping
succ = {a: [] for a in activities}
for a, info in activities.items():
    for p in info["pred"]:
        succ[p].append(a)
succ


{'A': ['B', 'C', 'D'],
 'B': ['E'],
 'C': ['F'],
 'D': ['F', 'H'],
 'E': ['G'],
 'F': ['G'],
 'G': ['I'],
 'H': ['I'],
 'I': []}

python
# backward pass: set LF for activities with no successors to project duration
LF = {}
LS = {}
project_duration = EF["I"]
# Process in reverse topological order
processed = set()
# Build topological ordering used: order list from forward pass 'ordered'? 
# Let's derive order: repeated earlier; to ensure stable, compute Kahn's algorithm
from collections import deque, defaultdict

pred_count = {a: len(info["pred"]) for a, info in activities.items()}
queue = deque([a for a in activities if pred_count[a]==0])
order = []
preds = {a: set(info["pred"]) for a, info in activities.items()}
while queue:
    n = queue.popleft()
    order.append(n)
    for s in succ[n]:
        preds[s].remove(n)
        if len(preds[s]) ==

['A', 'B', 'C', 'D', 'E', 'F', 'H', 'G', 'I']

python
# Now backward
LF = {a: float('inf') for a in activities}
LS = {}
for a in reversed(order):
    if len(succ[a])==0:
        LF[a] = project_duration
    else:
        LF[a] = min(LS[s] for s in succ[a])
    LS[a] = LF[a] - activities[a]["dur"]
LF, LS


({'A': 1, 'B': 5, 'C': 9, 'D': 9, 'E': 11, 'F': 11, 'G': 18, 'H': 18, 'I': 22},
 {'I': 18, 'G': 11, 'H': 9, 'F': 9, 'E': 5, 'D': 2, 'C': 6, 'B': 1, 'A': 0})

python
TF = {a: LS[a]-ES[a] for a in activities}
EF_ordered = {a: EF[a] for a in activities}
ES, EF, LS, LF, TF


({'A': 0, 'D': 1, 'B': 1, 'E': 5, 'H': 8, 'C': 1, 'F': 8, 'G': 11, 'I': 18},
 {'A': 1, 'D': 8, 'B': 5, 'E': 11, 'H': 17, 'C': 4, 'F': 10, 'G': 18, 'I': 22},
 {'I': 18, 'G': 11, 'H': 9, 'F': 9, 'E': 5, 'D': 2, 'C': 6, 'B': 1, 'A': 0},
 {'A': 1, 'B': 5, 'C': 9, 'D': 9, 'E': 11, 'F': 11, 'G': 18, 'H': 18, 'I': 22},
 {'A': 0, 'B': 0, 'C': 5, 'D': 1, 'E': 0, 'F': 1, 'G': 0, 'H': 1, 'I': 0})

python
activities2 = {**activities}
activities2["F"] = {"dur": 4, "pred": ["C","D"]}

# recompute forward
ES2, EF2 = {}, {}
remaining = set(activities2.keys())
while remaining:
    for act in list(remaining):
        preds = activities2[act]["pred"]
        if all(p in EF2 for p in preds):
            ES2[act] = max([EF2[p] for p in preds], default=0)
            EF2[act] = ES2[act] + activities2[act]["dur"]
            remaining.remove(act)
succ2 = {a: [] for a in activities2}
for a, info in activities2.items():
    for p in info["pred"]:
        succ2[p].append(a)

# topo order again 
from collections import deque
pred_count2 = {a: len(info["pred"]) for a, info in activities2.items()}
queue = deque([a for a in activities2 if pred_count2[a]==0])
order2 = []
preds2 = {a: set(info["pred"]) for a, info in activities2.items()}
while queue:
    n = queue.popleft()
    order2.append(n)
    for s in succ2[n]:
        preds2[s].remove(n)
        if len(preds2[s]) == 0:
            queue.append(s)

project_duration2 = EF2["I"]
LF2, LS2, TF2 = {}, {}, {}
LF2 = {a: float('inf') for a in activities2}
for a in reversed(order2):
    if len(succ2[a])==0:
        LF2[a] = project_duration2
    else:
        LF2[a] = min(LS2[s] for s in succ2[a])
    LS2[a] = LF2[a] - activities2[a]["dur"]
TF2 = {a: LS2[a]-ES2[a] for a in activities2}

ES2, EF2, LS2, LF2, TF2, project_duration2


({'A': 0, 'D': 1, 'B': 1, 'E': 5, 'H': 8, 'C': 1, 'F': 8, 'G': 12, 'I': 19},
 {'A': 1, 'D': 8, 'B': 5, 'E': 11, 'H': 17, 'C': 4, 'F': 12, 'G': 19, 'I': 23},
 {'I': 19, 'G': 12, 'H': 10, 'F': 8, 'E': 6, 'D': 1, 'C': 5, 'B': 2, 'A': 0},
 {'A': 1, 'B': 6, 'C': 8, 'D': 8, 'E': 12, 'F': 12, 'G': 19, 'H': 19, 'I': 23},
 {'A': 0, 'B': 1, 'C': 4, 'D': 0, 'E': 1, 'F': 0, 'G': 0, 'H': 2, 'I': 0},
 23)