Simulation Simplified
12. Multiple Knob Turning
Class P2Pedia06

import edu.rit.numeric.ListSeries;
import edu.rit.numeric.ListXYSeries;
import edu.rit.numeric.ListXYZSeries;
import edu.rit.numeric.Series;
import edu.rit.numeric.XYZSeries;
import edu.rit.numeric.plot.Dots;
import edu.rit.numeric.plot.Plot;
import edu.rit.numeric.plot.Strokes;
import edu.rit.util.Random;
import edu.rit.util.RandomSubset;
import java.util.Arrays;
import java.util.LinkedList;
public class P2Pedia06
   {
   public static void main
      (String[] args)
      throws Exception
      {
      if (args.length != 8) usage();
      double log_N_L = Double.parseDouble (args[0]);
      double log_N_U = Double.parseDouble (args[1]);
      double log_N_D = Double.parseDouble (args[2]);
      int K_L = Integer.parseInt (args[3]);
      int K_U = Integer.parseInt (args[4]);
      int K_D = Integer.parseInt (args[5]);
      int T = Integer.parseInt (args[6]);
      long seed = Long.parseLong (args[7]);
      Random prng = Random.getInstance (seed);
      Plot plot = new Plot()
         .plotTitle ("P2Pedia06, T="+T)
         .xAxisTitle ("Number of nodes, N")
         .yAxisTitle ("Mean query path length, Q")
         .xAxisKind (Plot.LOGARITHMIC)
         .xAxisMinorDivisions (10)
         .minorGridLines (true)
         .rightMargin (36)
         .labelPosition (Plot.RIGHT)
         .labelOffset (6);
      for (int K = K_L; K <= K_U; ++ K)
         {
         ListXYSeries mqpl = new ListXYSeries();
         ListXYZSeries model = new ListXYZSeries();
         System.out.printf ("========================%n");
         System.out.printf ("K = %d%n", K);
         System.out.printf ("\tQuery path length, Q%n");
         System.out.printf ("N\tMean\tStddev%n");
         double log_N;
         for (int r = 0; (log_N = log_N_L + r*log_N_D) <= log_N_U;
               ++ r)
            {
            int N = (int) (Math.pow(10.0,log_N) + 0.5);
            int[][] conn = new int[N][K+1];
            for (int i = 0; i < N; ++ i) conn[i][0] = (i + 1)%N;
            int[] dist = new int[N];
            ListSeries len = new ListSeries();
            for (int trial = 0; trial < T; ++ trial)
               {
               for (int i = 0; i < N; ++ i)
                  {
                  RandomSubset rs = new RandomSubset (prng, N)
                     .remove (i) .remove ((i + 1)%N);
                  for (int j = 1; j <= K; ++ j)
                     conn[i][j] = rs.next();
                  }
               int orig = prng.nextInt (N);
               int match = prng.nextInt (N);
               len.add (shortestPathLength
                  (conn, dist, orig, match));
               }
            Series.Stats stats = len.stats();
            System.out.printf ("%d\t%.2f\t%.2f%n",
               N, stats.mean, stats.stddev);
            mqpl.add (N, stats.mean);
            model.add (Math.log10(N), stats.mean, stats.stddev);
            }
         XYZSeries.Regression regr = model.linearRegression();
         System.out.printf ("Q = a + b log N%n");
         System.out.printf ("a = %.2f%n", regr.a);
         System.out.printf ("b = %.2f%n", regr.b);
         System.out.printf ("stddev(a) = %.2f%n",
            Math.sqrt(regr.var_a));
         System.out.printf ("stddev(b) = %.2f%n",
            Math.sqrt(regr.var_b));
         System.out.printf ("chi^2 = %.6f%n", regr.chi2);
         System.out.printf ("p-value = %.6f%n", regr.significance);
         plot.seriesDots (Dots.circle())
            .seriesStroke (null)
            .xySeries (mqpl)
            .seriesDots (null)
            .seriesStroke (Strokes.solid (1))
            .xySeries
               (Math.pow(10.0,log_N_L), regr.a + regr.b*log_N_L,
                Math.pow(10.0,log_N_U), regr.a + regr.b*log_N_U)
            .label ("K="+K,
                Math.pow(10.0,log_N_U), regr.a + regr.b*log_N_U);
         }
      plot.getFrame().setVisible (true);
      }

   private static int shortestPathLength
      (int[][] conn,
       int[] dist,
       int orig,
       int match)
      {
      if (orig == match) return 0;
      Arrays.fill (dist, -1);
      dist[orig] = 0;
      LinkedList<Integer> queue = new LinkedList<Integer>();
      queue.addLast (orig);
      for (;;)
         {
         int i = queue.removeFirst();
         for (int j : conn[i])
            {
            if (j == match)
               {
               return dist[i] + 1;
               }
            else if (dist[j] == -1)
               {
               dist[j] = dist[i] + 1;
               queue.addLast (j);
               }
            }
         }
      }

   private static void usage()
      {
      System.err.println
         ("Usage: java P2Pedia06 <log N_L> <log N_U> "+
          "<log N_D> <K_L> <K_U> <K_D> <T> <seed>");
      System.exit (1);
      }
   }