Ranks and the critical path

Compute the ranks used by list-scheduling algorithms.

Input format (used by all Chapter 6 labs):

n p                      (tasks, processors)
n lines: w(i,1) ... w(i,p)   (computation cost of task i on each processor)
m                        (number of edges)
m lines: i j c           (edge i -> j with communication cost c)

Tasks are numbered 1…n. Compute:

• average cost w̄ᵢ (mean over processors);
• rank_u(i) = w̄ᵢ + max over successors j of (c(i, j) + rank_u(j)); for exit tasks rank_u = w̄ᵢ;
• rank_d(i) = max over predecessors j of (rank_d(j) + w̄ⱼ + c(j, i)); for entry tasks rank_d = 0.

Print for each task Ti: avg w A, rank_u U, rank_d D, sum S (two decimals), then Critical path (CPOP): T1 -> T2 -> ... | length L, listing in increasing task number every task whose rank_u + rank_d equals the maximum sum (within 10⁻⁶).

Input:

5 2
4 6
5 3
6 8
3 5
4 2
5
1 2 2
1 3 3
2 5 4
3 4 1
4 5 2

Output:

T1: avg w 5.00, rank_u 25.00, rank_d 0.00, sum 25.00
T2: avg w 4.00, rank_u 11.00, rank_d 7.00, sum 18.00
T3: avg w 7.00, rank_u 17.00, rank_d 8.00, sum 25.00
T4: avg w 4.00, rank_u 9.00, rank_d 16.00, sum 25.00
T5: avg w 3.00, rank_u 3.00, rank_d 22.00, sum 25.00
Critical path (CPOP): T1 -> T3 -> T4 -> T5 | length 25.00