CI Pipeline Critical Path

1. Background Knowledge

This problem models a Directed Acyclic Graph (DAG) where nodes represent jobs and edges represent dependencies. The core concept is Critical Path Method (CPM), a project management technique used to determine the minimum time required to complete a project. In a CI/CD pipeline with unlimited parallel runners, the total execution time is dictated by the longest chain of dependent tasks, known as the critical path. Any delay in a critical job directly delays the entire pipeline, whereas non-critical jobs have slack (or float), meaning they can be delayed without affecting the final deadline.

To solve this, we utilize two fundamental passes over the DAG:

1. Forward Pass: Computes the Earliest Finish (EF) time for each job. This determines when a job can finish if all its predecessors finish as early as possible. The maximum EF across all jobs is the total pipeline duration.
2. Backward Pass: Computes the Latest Finish (LF) time for each job. This determines the latest a job can finish without delaying the overall pipeline completion time.

The slack of a job is defined as $LF(j) - EF(j)$. Jobs with zero slack are critical. Identifying these jobs allows engineers to prioritize optimization efforts effectively, as reducing the duration of non-critical jobs yields no benefit to the total wall-clock time.

2. Algorithm Approach

The standard approach for CPM involves Topological Sorting combined with dynamic programming-like updates. Since the graph is a DAG, we can process nodes in an order that respects dependencies.

1. Graph Construction: Convert the input list of jobs into an adjacency list representation. We need two views:

• adj: Maps a job to its dependents (children) for the backward pass.
• in_degree: Tracks the number of dependencies for each job to facilitate topological sorting.

2. Topological Sort (Kahn's Algorithm): Use a queue to process jobs with zero in-degree. This ensures we process jobs only after all their dependencies are resolved. This ordering is crucial for the forward pass.
3. Forward Pass: Iterate through the topological order. For each job, calculate its EF based on the maximum EF of its dependencies plus its own duration.
4. Backward Pass: Iterate through the reverse topological order. For each job, calculate its LF based on the minimum LF of its dependents minus their durations. Jobs with no dependents have an LF equal to the total pipeline time.
5. Slack Calculation: Compute slack for each job and filter those with zero slack.

3. Step-by-Step Strategy

1. Parse Input: Create a dictionary mapping job names to their properties (duration, needs). Also, build an adjacency list dependents where dependents[u] contains all jobs that need u.
2. Compute In-Degrees: Calculate the number of dependencies for each job. Initialize a queue with all jobs having zero in-degree.
3. Topological Sort & Forward Pass:

• Initialize EF dictionary with 0 for all jobs.
• While the queue is not empty, pop a job u.
• For each dependent v of u:
• Update EF[v] = max(EF[v], EF[u] + duration[u]).
• Decrement in_degree[v]. If it becomes 0, push v to the queue.
• Store the topological order in a list topo_order.

4. Determine Total Time: The total_minutes is the maximum value in the EF dictionary.
5. Backward Pass:

• Initialize LF dictionary. Set LF[j] = total_minutes for all jobs j that have no dependents (sinks). For others, initialize with infinity.
• Iterate through topo_order in reverse.
• For each job u, if it has dependents, update its LF: $LF(u) = \min_{v \in \text{dependents}(u)} (LF(v) - \text{duration}(v))$ Note: If a job has no dependents, its LF remains total_minutes.

6. Identify Critical Jobs:

• For each job, calculate slack = LF[j] - EF[j].
• Collect all job names where slack == 0.

7. Format Output: Sort the critical job names alphabetically and return the dictionary with total_minutes and critical_jobs.

4. Common Pitfalls

• Incorrect Backward Pass Initialization: Ensure that jobs with no dependents (leaf nodes in the dependency graph) are correctly initialized with LF = total_minutes. If you initialize all LF to infinity and only update via dependents, leaf nodes will remain infinity, leading to incorrect slack calculations.
• Reverse Topological Order: The backward pass must process nodes in reverse topological order. Processing in forward order would mean you try to calculate LF before the LF of dependents is known.
• Multiple Critical Paths: The problem states that all zero-slack jobs must be returned. Do not stop after finding one path. There may be parallel critical chains.
• Graph Cycles: Although the problem guarantees a DAG, always ensure your topological sort detects cycles in general cases. If the queue empties before all nodes are processed, a cycle exists.
• Indexing vs. Names: Be careful when mapping between job names and indices. Using a dictionary keyed by job name is often safer and cleaner than converting names to integer indices.

5. Time & Space Complexity

• Time Complexity: $O(V + E)$, where $V$ is the number of jobs and $E$ is the number of dependency edges.
• Building the graph and in-degrees takes $O(V + E)$.
• Topological sort (Kahn's algorithm) visits each node and edge once: $O(V + E)$.
• Forward and backward passes each iterate through all nodes and edges once: $O(V + E)$.
• Sorting the critical jobs takes $O(K \log K)$, where $K$ is the number of critical jobs ($K \le V$). This is dominated by $O(V + E)$.
• Space Complexity: $O(V + E)$.
• We store the adjacency list (dependents), in_degree array, EF and LF dictionaries, and the topological order list. All scale linearly with the size of the graph.