001package algs44;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac CPM.java
005 *  Execution:    java CPM < input.txt
006 *  Dependencies: EdgeWeightedDigraph.java AcyclicDigraphLP.java StdOut.java
007 *  Data files:   http://algs4.cs.princeton.edu/44sp/jobsPC.txt
008 *
009 *  Critical path method.
010 *
011 *  % java CPM < jobsPC.txt
012 *   job   start  finish
013 *  --------------------
014 *     0     0.0    41.0
015 *     1    41.0    92.0
016 *     2   123.0   173.0
017 *     3    91.0   127.0
018 *     4    70.0   108.0
019 *     5     0.0    45.0
020 *     6    70.0    91.0
021 *     7    41.0    73.0
022 *     8    91.0   123.0
023 *     9    41.0    70.0
024 *  Finish time:   173.0
025 *
026 *************************************************************************/
027
028public class CPM {
029
030        public static void main(String[] args) {
031                StdIn.fromFile ("data/jobsPC.txt");
032
033                // number of jobs
034                int N = StdIn.readInt();
035
036                // source and sink
037                int source = 2*N;
038                int sink   = 2*N + 1;
039
040                // build network
041                EdgeWeightedDigraph G = new EdgeWeightedDigraph(2*N + 2);
042                for (int i = 0; i < N; i++) {
043                        double duration = StdIn.readDouble();
044                        G.addEdge(new DirectedEdge(source, i, 0.0));
045                        G.addEdge(new DirectedEdge(i+N, sink, 0.0));
046                        G.addEdge(new DirectedEdge(i, i+N,    duration));
047
048                        // precedence constraints
049                        int M = StdIn.readInt();
050                        for (int j = 0; j < M; j++) {
051                                int precedent = StdIn.readInt();
052                                G.addEdge(new DirectedEdge(N+i, precedent, 0.0));
053                        }
054                }
055
056                // compute longest path
057                AcyclicLP lp = new AcyclicLP(G, source);
058
059                // print results
060                StdOut.println(" job   start  finish");
061                StdOut.println("--------------------");
062                for (int i = 0; i < N; i++) {
063                        StdOut.format("%4d %7.1f %7.1f\n", i, lp.distTo(i), lp.distTo(i+N));
064                }
065                StdOut.format("Finish time: %7.1f\n", lp.distTo(sink));
066        }
067
068}