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
  43 #include "sn_network.h"
  44 #include "sn_random.h"
  45
  46 #if !defined(__GNUC__) || !__GNUC__
  47 # define __attribute__(x) /**/
  48 #endif
  49
  50 static int inputs_num = 16;
  51
  52 static char *initial_input_file = NULL;
  53 static char *best_output_file = NULL;
  54
  55 static sn_network_t *best_solution = NULL;
  56 static int best_rating = INT_MAX;
  57
  58 static _Bool do_loop = 1;
  59
  60 static void sigint_handler (int signal __attribute__((unused)))
  61 {
  62   do_loop = 0;
  63 } /* void sigint_handler */
  64
  65 static void exit_usage (const char *name, int status)
  66 {
  67   printf ("Usage: %s [options]\n"
  68       "\n"
  69       "Valid options are:\n"
  70       "  -i <file>     Initial input file (REQUIRED)\n"
  71       "  -o <file>     Write the current best solution to <file>\n"
  72       "  -h            Display usage information (this message)\n"
  73       "\n",
  74       name);
  75   exit (status);
  76 } /* void exit_usage */
  77
  78 int read_options (int argc, char **argv)
  79 {
  80   int option;
  81
  82   while ((option = getopt (argc, argv, "i:o:p:P:s:t:h")) != -1)
  83   {
  84     switch (option)
  85     {
  86       case 'i':
  87       {
  88         if (initial_input_file != NULL)
  89           free (initial_input_file);
  90         initial_input_file = strdup (optarg);
  91         break;
  92       }
  93
  94       case 'o':
  95       {
  96         if (best_output_file != NULL)
  97           free (best_output_file);
  98         best_output_file = strdup (optarg);
  99         break;
 100       }
 101
 102       case 'h':
 103       default:
 104         exit_usage (argv[0], EXIT_SUCCESS);
 105     }
 106   }
 107
 108   return (0);
 109 } /* int read_options */
 110
 111 static int rate_network (const sn_network_t *n)
 112 {
 113   int rate;
 114   int i;
 115
 116   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
 117   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
 118   {
 119     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
 120     rate += SN_STAGE_COMP_NUM (s);
 121   }
 122
 123   return (rate);
 124 } /* int rate_network */
 125
 126 static sn_network_t *get_next (sn_network_t *n)
 127 {
 128   sn_network_t *nleft;
 129   sn_network_t *nright;
 130   sn_network_t *nret;
 131
 132   if (n == NULL)
 133     return (NULL);
 134
 135   nleft = sn_network_clone (n);
 136   nright = sn_network_clone (n);
 137
 138   assert (nleft != NULL);
 139   assert (nright != NULL);
 140
 141   /* combine the two parents */
 142   nret = sn_network_combine (nleft, nright);
 143
 144   sn_network_destroy (nleft);
 145   sn_network_destroy (nright);
 146
 147   /* randomly chose an input and do a min- or max-cut. */
 148   while (SN_NETWORK_INPUT_NUM (nret) > inputs_num)
 149   {
 150     int pos;
 151     enum sn_network_cut_dir_e dir;
 152
 153     pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (nret) - 1);
 154     dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
 155
 156     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (nret)));
 157
 158     sn_network_cut_at (nret, pos, dir);
 159   }
 160
 161   /* compress the network to get a compact representation */
 162   sn_network_compress (nret);
 163
 164   assert (SN_NETWORK_INPUT_NUM (nret) == inputs_num);
 165   return (nret);
 166 } /* sn_network_t *get_next */
 167
 168 static void random_walk (sn_network_t *n)
 169 {
 170   uint64_t iteration_counter = 0;
 171
 172   while (do_loop)
 173   {
 174     sn_network_t *next = get_next (n);
 175     int rating;
 176
 177     if (next == NULL)
 178     {
 179       fprintf (stderr, "get_next() failed.\n");
 180       return;
 181     }
 182
 183     rating = rate_network (next);
 184     if (rating < best_rating)
 185     {
 186       printf ("New best rating (%i) after %"PRIu64" iterations.\n",
 187           rating, iteration_counter);
 188
 189       best_rating = rating;
 190       sn_network_destroy (best_solution);
 191       best_solution = sn_network_clone (next);
 192     }
 193
 194     sn_network_destroy (n);
 195     n = next;
 196     iteration_counter++;
 197   } /* while (do_loop) */
 198
 199   sn_network_destroy (n);
 200
 201   printf ("Exiting after %"PRIu64" iterations.\n", iteration_counter);
 202 } /* void random_walk */
 203
 204 int main (int argc, char **argv)
 205 {
 206   sn_network_t *start_network;
 207
 208   struct sigaction sigint_action;
 209   struct sigaction sigterm_action;
 210
 211   read_options (argc, argv);
 212   if (initial_input_file == NULL)
 213     exit_usage (argv[0], EXIT_FAILURE);
 214
 215   memset (&sigint_action, '\0', sizeof (sigint_action));
 216   sigint_action.sa_handler = sigint_handler;
 217   sigaction (SIGINT, &sigint_action, NULL);
 218
 219   memset (&sigterm_action, '\0', sizeof (sigterm_action));
 220   sigterm_action.sa_handler = sigint_handler;
 221   sigaction (SIGTERM, &sigterm_action, NULL);
 222
 223   start_network = sn_network_read_file (initial_input_file);
 224   if (start_network == NULL)
 225   {
 226     printf ("start_network == NULL\n");
 227     exit (EXIT_FAILURE);
 228   }
 229
 230   inputs_num = SN_NETWORK_INPUT_NUM(start_network);
 231
 232   printf ("Current configuration:\n"
 233       "  Initial network:  %s\n"
 234       "  Number of inputs: %3i\n"
 235       "=======================\n",
 236       initial_input_file, inputs_num);
 237
 238   random_walk (start_network);
 239   start_network = NULL;
 240
 241   if (best_solution != NULL)
 242   {
 243     if (best_output_file != NULL)
 244       sn_network_write_file (best_solution, best_output_file);
 245
 246     printf ("=== Best solution (rating: %i) ===\n", best_rating);
 247     sn_network_normalize (best_solution);
 248     sn_network_show (best_solution);
 249     sn_network_destroy (best_solution);
 250   }
 251
 252   exit (EXIT_SUCCESS);
 253   return (0);
 254 } /* int main */
 255
 256 /* vim: set shiftwidth=2 softtabstop=2 : */