src/sn-markov.c

   1 /**
   2  * libsortnetwork - src/sn-markov.c
   3  * Copyright (C) 2008-2010  Florian octo Forster
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; only version 2 of the License is applicable.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  17  *
  18  * Authors:
  19  *   Florian octo Forster <ff at octo.it>
  20  **/
  21
  22 #ifndef _ISOC99_SOURCE
  23 # define _ISOC99_SOURCE
  24 #endif
  25 #ifndef _POSIX_C_SOURCE
  26 # define _POSIX_C_SOURCE 200809L
  27 #endif
  28 #ifndef _XOPEN_SOURCE
  29 # define _XOPEN_SOURCE 700
  30 #endif
  31
  32 #include <stdlib.h>
  33 #include <stdio.h>
  34 #include <stdint.h>
  35 #include <inttypes.h>
  36 #include <string.h>
  37
  38 #include <unistd.h>
  39 #include <signal.h>
  40 #include <assert.h>
  41 #include <limits.h>
  42 #include <errno.h>
  43
  44 #include "sn_network.h"
  45 #include "sn_random.h"
  46 #include "histogram.h"
  47
  48 #if !defined(__GNUC__) || !__GNUC__
  49 # define __attribute__(x) /**/
  50 #endif
  51
  52 static int inputs_num = 16;
  53 static _Bool use_bitonic = 0;
  54
  55 static char *initial_input_file = NULL;
  56 static char *best_output_file = NULL;
  57
  58 static sn_network_t *best_solution = NULL;
  59 static int best_rating = INT_MAX;
  60
  61 static _Bool do_loop = 1;
  62 static uint64_t max_iterations = 0;
  63
  64 static histogram_t *histogram;
  65
  66 static void sigint_handler (int signal __attribute__((unused)))
  67 {
  68   do_loop = 0;
  69 } /* void sigint_handler */
  70
  71 static void exit_usage (const char *name, int status)
  72 {
  73   printf ("Usage: %s [options]\n"
  74       "\n"
  75       "Valid options are:\n"
  76       "  -i <file>     Initial input file (REQUIRED)\n"
  77       "  -o <file>     Write the current best solution to <file>\n"
  78       "  -n <number>   Maximum number of steps (iterations) to perform\n"
  79       "  -b            Use the bitonic merger instead of the odd-even merger\n"
  80       "  -h            Display usage information (this message)\n"
  81       "\n",
  82       name);
  83   exit (status);
  84 } /* void exit_usage */
  85
  86 int read_options (int argc, char **argv)
  87 {
  88   int option;
  89
  90   while ((option = getopt (argc, argv, "i:o:n:bh")) != -1)
  91   {
  92     switch (option)
  93     {
  94       case 'i':
  95       {
  96         if (initial_input_file != NULL)
  97           free (initial_input_file);
  98         initial_input_file = strdup (optarg);
  99         break;
 100       }
 101
 102       case 'o':
 103       {
 104         if (best_output_file != NULL)
 105           free (best_output_file);
 106         best_output_file = strdup (optarg);
 107         break;
 108       }
 109
 110       case 'n':
 111       {
 112         errno = 0;
 113         max_iterations = (uint64_t) strtoull (optarg,
 114             /* endptr = */ NULL,
 115             /* base   = */ 0);
 116         if (errno != 0)
 117         {
 118           fprintf (stderr, "Parsing integer argument failed: %s\n",
 119               strerror (errno));
 120           exit_usage (argv[0], EXIT_FAILURE);
 121         }
 122         break;
 123       }
 124
 125       case 'b':
 126       use_bitonic = 1;
 127       break;
 128
 129       case 'h':
 130       default:
 131         exit_usage (argv[0], EXIT_SUCCESS);
 132     }
 133   }
 134
 135   return (0);
 136 } /* int read_options */
 137
 138 static int rate_network (const sn_network_t *n)
 139 {
 140   int rate;
 141
 142   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
 143   rate += sn_network_get_comparator_num (n);
 144
 145   return (rate);
 146 } /* int rate_network */
 147
 148 static sn_network_t *get_next (sn_network_t *n)
 149 {
 150   sn_network_t *nleft;
 151   sn_network_t *nright;
 152   sn_network_t *nret;
 153
 154   if (n == NULL)
 155     return (NULL);
 156
 157   nleft = sn_network_clone (n);
 158   nright = sn_network_clone (n);
 159
 160   assert (nleft != NULL);
 161   assert (nright != NULL);
 162
 163   /* combine the two parents */
 164   if (use_bitonic)
 165     nret = sn_network_combine_bitonic_merge (nleft, nright);
 166   else
 167     nret = sn_network_combine_odd_even_merge (nleft, nright);
 168
 169   sn_network_destroy (nleft);
 170   sn_network_destroy (nright);
 171
 172   /* randomly chose an input and do a min- or max-cut. */
 173   while (SN_NETWORK_INPUT_NUM (nret) > inputs_num)
 174   {
 175     int pos;
 176     enum sn_network_cut_dir_e dir;
 177
 178     pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (nret) - 1);
 179     dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
 180
 181     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (nret)));
 182
 183     sn_network_cut_at (nret, pos, dir);
 184   }
 185
 186   /* compress the network to get a compact representation */
 187   sn_network_compress (nret);
 188
 189   assert (SN_NETWORK_INPUT_NUM (nret) == inputs_num);
 190   return (nret);
 191 } /* sn_network_t *get_next */
 192
 193 static void random_walk (sn_network_t *n)
 194 {
 195   uint64_t iteration_counter = 0;
 196
 197   while (do_loop)
 198   {
 199     sn_network_t *next = get_next (n);
 200     int rating;
 201
 202     if (next == NULL)
 203     {
 204       fprintf (stderr, "get_next() failed.\n");
 205       return;
 206     }
 207
 208     rating = rate_network (next);
 209     if (rating < best_rating)
 210     {
 211       printf ("New best rating (%i) after %"PRIu64" iterations.\n",
 212           rating, iteration_counter);
 213
 214       best_rating = rating;
 215       sn_network_destroy (best_solution);
 216       best_solution = sn_network_clone (next);
 217     }
 218
 219     hist_account (histogram, sn_network_get_comparator_num (next));
 220
 221     sn_network_destroy (n);
 222     n = next;
 223     iteration_counter++;
 224
 225     if ((max_iterations > 0) && (iteration_counter >= max_iterations))
 226       break;
 227   } /* while (do_loop) */
 228
 229   sn_network_destroy (n);
 230
 231   printf ("Exiting after %"PRIu64" iterations.\n", iteration_counter);
 232 } /* void random_walk */
 233
 234 int main (int argc, char **argv)
 235 {
 236   sn_network_t *start_network;
 237
 238   struct sigaction sigint_action;
 239   struct sigaction sigterm_action;
 240
 241   histogram = hist_create ();
 242
 243   read_options (argc, argv);
 244   if (initial_input_file == NULL)
 245     exit_usage (argv[0], EXIT_FAILURE);
 246
 247   memset (&sigint_action, '\0', sizeof (sigint_action));
 248   sigint_action.sa_handler = sigint_handler;
 249   sigaction (SIGINT, &sigint_action, NULL);
 250
 251   memset (&sigterm_action, '\0', sizeof (sigterm_action));
 252   sigterm_action.sa_handler = sigint_handler;
 253   sigaction (SIGTERM, &sigterm_action, NULL);
 254
 255   start_network = sn_network_read_file (initial_input_file);
 256   if (start_network == NULL)
 257   {
 258     printf ("start_network == NULL\n");
 259     exit (EXIT_FAILURE);
 260   }
 261
 262   inputs_num = SN_NETWORK_INPUT_NUM(start_network);
 263
 264   printf ("Current configuration:\n"
 265       "  Initial network:  %s\n"
 266       "  Number of inputs: %3i\n"
 267       "=======================\n",
 268       initial_input_file, inputs_num);
 269
 270   random_walk (start_network);
 271   start_network = NULL;
 272
 273   hist_print (histogram);
 274   hist_destroy (histogram);
 275   histogram = NULL;
 276
 277   if (best_solution != NULL)
 278   {
 279     if (best_output_file != NULL)
 280       sn_network_write_file (best_solution, best_output_file);
 281
 282     printf ("=== Best solution (rating: %i) ===\n", best_rating);
 283     sn_network_normalize (best_solution);
 284     sn_network_show (best_solution);
 285     sn_network_destroy (best_solution);
 286   }
 287
 288   exit (EXIT_SUCCESS);
 289   return (0);
 290 } /* int main */
 291
 292 /* vim: set shiftwidth=2 softtabstop=2 : */