Simulation Simplified
10. Knob Turning
Class P2Pedia04

import edu.rit.numeric.ListSeries;
import edu.rit.numeric.ListXYSeries;
import edu.rit.numeric.Series;
import edu.rit.numeric.plot.Plot;
import edu.rit.util.Random;
import edu.rit.util.RandomSubset;
import java.util.Arrays;
import java.util.LinkedList;
public class P2Pedia04
   {
   public static void main
      (String[] args)
      throws Exception
      {
      if (args.length != 6) usage();
      int N_L = Integer.parseInt (args[0]);
      int N_U = Integer.parseInt (args[1]);
      int N_D = Integer.parseInt (args[2]);
      int K = Integer.parseInt (args[3]);
      int T = Integer.parseInt (args[4]);
      long seed = Long.parseLong (args[5]);
      Random prng = Random.getInstance (seed);
      ListXYSeries mqpl = new ListXYSeries();
      System.out.printf ("\tQuery path length%n");
      System.out.printf ("N\tMean\tStddev%n");
      for (int N = N_L; N <= N_U; N += N_D)
         {
         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);
         }
      new Plot()
         .plotTitle ("P2Pedia04, K="+K+", T="+T)
         .xAxisTitle ("Number of nodes, N")
         .yAxisTitle ("Mean query path length")
         .xySeries (mqpl)
         .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 P2Pedia04 <N_L> <N_U> <N_D> <K> <T> <seed>");
      System.exit (1);
      }
   }