sn-markov: Implement the "-b" option.

[sort-networks.git] / src / sn-markov.c

diff --git a/src/sn-markov.c b/src/sn-markov.c
index 89e293b..b1f3008 100644 (file)
--- a/src/sn-markov.c
+++ b/src/sn-markov.c
@@ -39,15 +39,18 @@
 #include <signal.h>
 #include <assert.h>
 #include <limits.h>
+#include <errno.h>
 
 #include "sn_network.h"
 #include "sn_random.h"
+#include "histogram.h"
 
 #if !defined(__GNUC__) || !__GNUC__
 # define __attribute__(x) /**/
 #endif
 
 static int inputs_num = 16;
+static _Bool use_bitonic = 0;
 
 static char *initial_input_file = NULL;
 static char *best_output_file = NULL;
@@ -56,6 +59,9 @@ static sn_network_t *best_solution = NULL;
 static int best_rating = INT_MAX;
 
 static _Bool do_loop = 1;
+static uint64_t max_iterations = 0;
+
+static histogram_t *histogram;
 
 static void sigint_handler (int signal __attribute__((unused)))
 {
@@ -69,6 +75,8 @@ static void exit_usage (const char *name, int status)
       "Valid options are:\n"
       "  -i <file>     Initial input file (REQUIRED)\n"
       "  -o <file>     Write the current best solution to <file>\n"
+      "  -n <number>   Maximum number of steps (iterations) to perform\n"
+      "  -b            Use the bitonic merger instead of the odd-even merger\n"
       "  -h            Display usage information (this message)\n"
       "\n",
       name);
@@ -79,7 +87,7 @@ int read_options (int argc, char **argv)
 {
   int option;
 
-  while ((option = getopt (argc, argv, "i:o:p:P:s:t:h")) != -1)
+  while ((option = getopt (argc, argv, "i:o:n:bh")) != -1)
   {
     switch (option)
     {
@@ -99,6 +107,25 @@ int read_options (int argc, char **argv)
        break;
       }
 
+      case 'n':
+      {
+       errno = 0;
+       max_iterations = (uint64_t) strtoull (optarg,
+           /* endptr = */ NULL,
+           /* base   = */ 0);
+       if (errno != 0)
+       {
+         fprintf (stderr, "Parsing integer argument failed: %s\n",
+             strerror (errno));
+         exit_usage (argv[0], EXIT_FAILURE);
+       }
+       break;
+      }
+
+      case 'b':
+      use_bitonic = 1;
+      break;
+
       case 'h':
       default:
        exit_usage (argv[0], EXIT_SUCCESS);
@@ -111,14 +138,9 @@ int read_options (int argc, char **argv)
 static int rate_network (const sn_network_t *n)
 {
   int rate;
-  int i;
 
   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
-  for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
-  {
-    sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
-    rate += SN_STAGE_COMP_NUM (s);
-  }
+  rate += sn_network_get_comparator_num (n);
 
   return (rate);
 } /* int rate_network */
@@ -139,7 +161,10 @@ static sn_network_t *get_next (sn_network_t *n)
   assert (nright != NULL);
 
   /* combine the two parents */
-  nret = sn_network_combine (nleft, nright);
+  if (use_bitonic)
+    nret = sn_network_combine_bitonic_merge (nleft, nright);
+  else
+    nret = sn_network_combine_odd_even_merge (nleft, nright);
 
   sn_network_destroy (nleft);
   sn_network_destroy (nright);
@@ -191,9 +216,14 @@ static void random_walk (sn_network_t *n)
       best_solution = sn_network_clone (next);
     }
 
+    hist_account (histogram, sn_network_get_comparator_num (next));
+
     sn_network_destroy (n);
     n = next;
     iteration_counter++;
+
+    if ((max_iterations > 0) && (iteration_counter >= max_iterations))
+      break;
   } /* while (do_loop) */
 
   sn_network_destroy (n);
@@ -208,6 +238,8 @@ int main (int argc, char **argv)
   struct sigaction sigint_action;
   struct sigaction sigterm_action;
 
+  histogram = hist_create ();
+
   read_options (argc, argv);
   if (initial_input_file == NULL)
     exit_usage (argv[0], EXIT_FAILURE);
@@ -238,6 +270,10 @@ int main (int argc, char **argv)
   random_walk (start_network);
   start_network = NULL;
 
+  hist_print (histogram);
+  hist_destroy (histogram);
+  histogram = NULL;
+
   if (best_solution != NULL)
   {
     if (best_output_file != NULL)