edu.princeton.cs.algs4

Class CPM

java.lang.Object

edu.princeton.cs.algs4.CPM

public class CPM
extends java.lang.Object

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 AcyclicLP 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.

For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Method Summary

Modifier and Type	Method and Description
static void	main(java.lang.String[] args) Reads the precedence constraints from standard input and prints a feasible schedule to standard output.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

main

public static void main(java.lang.String[] args)

Reads the precedence constraints from standard input and prints a feasible schedule to standard output.

Parameters:

args - the command-line arguments