The CPM class provides a client that solves the parallel precedence-constrained job scheduling problem via the Critical path method. It reduces the problem to the longest-paths problem in edge-weighted DAGs. It builds an edge-weighted digraph (which must be a DAG) from the job-scheduling problem specification, finds the longest-paths tree, and computes the longest-paths lengths (which are precisely the start times for each job).

This implementation uses to find a longest path in a DAG. The running time is proportional to V + E, where V is the number of jobs and E is the number of precedence constraints.