Critical Path Length of a Pipeline DAG
Problem Statement
Compute the minimum total time to run a CI pipeline where independent stages run in parallel — the critical path (longest-duration path) through the dependency DAG.
Background
Each stage has a duration and depends on prior stages. A stage cannot start until all its dependencies finish. The earliest finish time of a stage is duration + max(earliest finish of its deps) (or just its duration if it has none). The pipeline's makespan is the maximum finish time over all stages.
Your Task
def critical_path(stages):
- stages: dict mapping name -> {"duration": number, "deps": [names]}.
- Return the makespan (number). Assume the DAG is acyclic.
Input Format
- stages (dict).
Output Format
- A number (total time).
Sample
print(critical_path({"a": {"duration": 3, "deps": []}, "b": {"duration": 4, "deps": ["a"]}}))
Output:
7
Example:
print(critical_path({"a": {"duration": 3, "deps": []}, "b": {"duration": 4, "deps": ["a"]}}))7
- Identify the dependency chain: Stage "b" depends on stage "a", so "a" must finish before "b" can start.
- Calculate the earliest finish time for stage "a": Since it has no dependencies, its finish time is simply its duration, 3.
- Calculate the earliest finish time for stage "b": It waits for its dependency "a" to finish, so its start time is 3; adding its own duration gives 3+4=7.
- Determine the pipeline makespan: This is the maximum finish time across all stages, which is max(3,7)=7.
- The final output is 7
Constraints:
- finish(stage) = duration + max(finish(dep)) (0 if no deps).
- Makespan = max finish over all stages.
- DAG is acyclic; use memoization.
1. Background Knowledge
This problem models a Directed Acyclic Graph (DAG) where nodes represent pipeline stages and edges represent dependencies. In a CI/CD context, a stage cannot begin until every stage it depends on has completed. The goal is to find the critical path, which is the longest path through the graph in terms of total duration. This path determines the makespan, or the minimum total time required to complete the entire pipeline, because all other paths will finish earlier or simultaneously.
The key insight is that the earliest finish time of a node is not simply the sum of its dependencies' times, but rather its own duration plus the maximum earliest finish time among all its dependencies. If a stage has no dependencies, its earliest finish time is just its own duration. This is a classic example of dynamic programming on a DAG, where the optimal substructure allows us to compute the answer for each node based on the answers of its predecessors.
Because the graph is guaranteed to be acyclic, we can process nodes in a specific order (topological order) to ensure that when we compute a node's value, all its dependencies have already been computed. This avoids the need for cycle detection or recursion depth management that would be required for general graphs.
2. Algorithm Approach
The standard approach is Topological Sort combined with Dynamic Programming.
- Topological Sort: Determine an ordering of the nodes such that for every directed edge u→v, node u comes before node v in the ordering. This can be done using Kahn's algorithm (BFS-based) or DFS-based post-order traversal.
- DP Traversal: Iterate through the nodes in topological order. For each node, calculate its earliest finish time using the formula:
If a node has no dependencies, the max term is 0. 3. Result Extraction: The makespan is the maximum value in the finish array across all nodes.
This approach ensures that when we process a node, all its dependencies have already been processed, so their finish times are known.
3. Step-by-Step Strategy
- Build the Graph:
- Create an adjacency list or simply use the input dictionary directly.
- Calculate the in-degree for each node (number of dependencies).
- Identify all nodes with in-degree 0 (no dependencies).
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.