pert_samplesol.java

（运筹学）运用我上传的graph class文件来解决网络图的问题

import java.util.*;
import java.io.*;

public class Pert{

    public static void main(String[] arg) throws Exception{

	/* ------------ PART 1: read in file and set up graph  ------------- */

	System.out.println("PERT: reading data file: case102.dat");

	FileReader file = new FileReader("case102.dat");
	BufferedReader in = new BufferedReader(file);
	Graph g = new Graph(100,100);
	try{
	    g.quiet();
	}catch(Throwable e){}
	
	String line="", item="", name;
	double o, p, m;
	String[] namel = new String[80];
	double[] pl = new double[80];
	double[] ml = new double[80];
	double[] ol = new double[80];
	Random r = new Random(12); 
	int vert = 0;

	System.out.println("PERT: constructing graph");

	while(in.ready()){ /* while more lines in file */
	    line = in.readLine();  /* read a line */
	    StringTokenizer data = new StringTokenizer(line);
                           	    /* and tokenize it */
	    name = data.nextToken();  /* this is the next activity */

	    o =  new Double(data.nextToken()).doubleValue();
	    m =  new Double(data.nextToken()).doubleValue();
	    p =  new Double(data.nextToken()).doubleValue();
	    /* Save name of activity and the three duration estimates in 
	       arrays for later use (in part 3) */
	    namel[vert] = name;
	    ol[vert] = o;
	    ml[vert] = m;
	    pl[vert] = p;
	    vert++;

	    /* add start and end node for activity to graph */
	    g.addVertex(name+"_start");
	    g.addVertex(name+"_end");
	    /* add edge from start to end node to graph */
	    g.addEdge(name+"_start", name+"_end", m);

	    /* any more items on line ? */
	    while(data.hasMoreTokens()){
		item = data.nextToken();
		/* Then put an edge from end node of the item to start node
		   of current activity (length=0) onto graph */
		g.addEdge(item+"_end", name+"_start", 0);
	    }
	}
	/* close the file */
	in.close();
	file.close();
	
	/* calculate critical path */
	g.criticalPath();

	/* get critical path and print it on screen */
	System.out.println("PERT: Critical path is:"); 
	String point = "0_start";
	do{
	    System.out.println(point+" : "+g.lengthFrom(point));
	    point = g.next(point);
	}while(point!=null);
	
	/* ------------ PART 3: randomized graph ------------------ */

	if (arg.length>0){

	System.out.println("PERT: Find critical paths for 10000 random graphs");
	double mean, stdv, cost;
	int i, j;
	int[] below = new int[60];
	double sum=0, sumsq=0,length;

	/* Do 10000 simulations */
	for(i=0;i<10000;i++){

	    // for each activity
	    for(j=0;j<vert;j++){
		// get mean and standard deviation
		mean = (ol[j]+4*ml[j]+pl[j])/6;
		stdv = (ol[j] - pl[j])/6;
		// sample a random variable with specified mean/std.dev.
		cost = stdv*r.nextGaussian()+mean;
		// and set new duration for activity
		g.newCost(namel[j]+"_start",namel[j]+"_end", cost); 
	    }
	    
	    // get critical path
	    g.criticalPath();
	    // record length of critical path
	    length = g.lengthFrom("0_start");
	    // record sum of all lengths and sum of all squared lengths
	    // NOTE: variance can be obtained by 
	    //           var(x) =  (sum (x_i)^2)/n - ((sum x_i)/n)^2
	    //       this way don't need to remember all values, but only
	    //       need to get sum x_i and sum (x_i)^2
	    sum += length;
	    sumsq += length*length;
	    // find the correct bracket for the length and increase the counter
	    // for the histogram
	    for(j=0;j<60;j++) 
		if (length<=j&&length>j-1) below[j]++;
	}

	/* print mean, variance and standard deviation */

	System.out.println("PERT: print statistics and histogram");
	System.out.println("Mean = "+sum/10000);
	System.out.println("Var  = "+(sumsq/10000 - (sum/10000)*(sum/10000)));
	System.out.println("Std.Dev. = "+
			   Math.sqrt(sumsq/10000 - (sum/10000)*(sum/10000)));

	// print out histogram
	for(i=0;i<60;i++){
	    System.out.println(i + " "+below[i]);}

	}
    }
    /*
      33 0
      34 1
      35 4
      36 18
      37 41
      38 129
      39 256
      40 576
      41 926
      42 1235
      43 1526
      44 1594
      45 1430
      46 1021
      47 642
      48 330
      49 176
      50 67
      51 20
      52 8
      53 0
      54 0
    */

}