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 3537023..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;
@@ -58,6 +61,8 @@ 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)))
 {
   do_loop = 0;
@@ -71,6 +76,7 @@ static void exit_usage (const char *name, int status)
       "  -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);
@@ -81,7 +87,7 @@ int read_options (int argc, char **argv)
 {
   int option;
 
-  while ((option = getopt (argc, argv, "i:o:n:h")) != -1)
+  while ((option = getopt (argc, argv, "i:o:n:bh")) != -1)
   {
     switch (option)
     {
@@ -116,6 +122,10 @@ int read_options (int argc, char **argv)
        break;
       }
 
+      case 'b':
+      use_bitonic = 1;
+      break;
+
       case 'h':
       default:
        exit_usage (argv[0], EXIT_SUCCESS);
@@ -151,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);
@@ -203,6 +216,8 @@ 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++;
@@ -223,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);
@@ -253,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)