src/sn-count-markov.c

   1 /**
   2  * libsortnetwork - src/sn-count-markov.c
   3  * Copyright (C) 2008-2011  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 <glib.h>
  45
  46 #include "sn_network.h"
  47 #include "sn_random.h"
  48
  49 #if !defined(__GNUC__) || !__GNUC__
  50 # define __attribute__(x) /**/
  51 #endif
  52
  53 static int inputs_num = 16;
  54
  55 static char *initial_input_file = NULL;
  56
  57 static GTree *all_networks = NULL;
  58 static uint64_t cycles_num = 0;
  59
  60 static _Bool do_loop = 1;
  61 static _Bool do_output_network = 0;
  62 static uint64_t max_iterations = 0;
  63
  64 static void sigint_handler (__attribute__((unused)) int signal) /* {{{ */
  65 {
  66   do_loop = 0;
  67 } /* }}} void sigint_handler */
  68
  69 static void sighup_handler (__attribute__((unused)) int signal) /* {{{ */
  70 {
  71   do_output_network = 1;
  72 } /* }}} void sighup_handler */
  73
  74 static int output_network (sn_network_t *n) /* {{{ */
  75 {
  76   FILE *fh;
  77
  78   if (n == NULL)
  79     return (EINVAL);
  80
  81   fh = fopen ("/dev/tty", "w");
  82   if (fh == NULL)
  83     return (errno);
  84
  85   sn_network_show_fh (n, fh);
  86
  87   fclose (fh);
  88   return (0);
  89 } /* }}} int output_network */
  90
  91 static gint compare_hashval (gconstpointer p0, gconstpointer p1) /* {{{ */
  92 {
  93   const uint64_t *i0 = (gconstpointer) p0;
  94   const uint64_t *i1 = (gconstpointer) p1;
  95
  96   if ((*i0) < (*i1))
  97     return (-1);
  98   else if ((*i0) > (*i1))
  99     return (1);
 100   else
 101     return (0);
 102 } /* }}} gint account_network_compare */
 103
 104 static int account_network (const sn_network_t *n, uint64_t iteration) /* {{{ */
 105 {
 106   uint64_t  key;
 107   uint64_t *key_ptr;
 108   uint64_t *value_ptr;
 109
 110   if (n == NULL)
 111     return (EINVAL);
 112
 113   if (iteration == 0)
 114   {
 115     printf ("# prev_iter this_iter cyclelength hashval\n");
 116     fflush (stdout);
 117   }
 118
 119   key = sn_network_get_hashval (n);
 120   key_ptr = &key;
 121
 122   value_ptr = (uint64_t *) g_tree_lookup (all_networks, (gconstpointer) key_ptr);
 123   if (value_ptr != NULL)
 124   {
 125     uint64_t cycle_length = iteration - (*value_ptr);
 126     printf ("%"PRIu64" %"PRIu64" %"PRIu64" 0x%016"PRIx64"\n",
 127         (*value_ptr), iteration, cycle_length, key);
 128     fflush (stdout);
 129
 130     cycles_num++;
 131     *value_ptr = iteration;
 132
 133     sn_random_init ();
 134
 135     return (0);
 136   }
 137
 138   key_ptr = malloc (sizeof (*key_ptr));
 139   if (key_ptr == NULL)
 140     return (ENOMEM);
 141   *key_ptr = key;
 142
 143   value_ptr = malloc (sizeof (*value_ptr));
 144   if (value_ptr == NULL)
 145   {
 146     free (key_ptr);
 147     return (ENOMEM);
 148   }
 149   *value_ptr = iteration;
 150
 151   g_tree_insert (all_networks, (gpointer) key_ptr, (gpointer) value_ptr);
 152   return (0);
 153 } /* }}} int account_network */
 154
 155 static void exit_usage (const char *name, int status)
 156 {
 157   printf ("Usage: %s [options]\n"
 158       "\n"
 159       "Valid options are:\n"
 160       "  -i <file>     Initial input file (REQUIRED)\n"
 161       "  -o <file>     Write the current best solution to <file>\n"
 162       "  -n <number>   Maximum number of steps (iterations) to perform\n"
 163       "  -h            Display usage information (this message)\n"
 164       "\n",
 165       name);
 166   exit (status);
 167 } /* void exit_usage */
 168
 169 int read_options (int argc, char **argv)
 170 {
 171   int option;
 172
 173   while ((option = getopt (argc, argv, "i:o:n:h")) != -1)
 174   {
 175     switch (option)
 176     {
 177       case 'i':
 178       {
 179         if (initial_input_file != NULL)
 180           free (initial_input_file);
 181         initial_input_file = strdup (optarg);
 182         break;
 183       }
 184
 185       case 'n':
 186       {
 187         errno = 0;
 188         max_iterations = (uint64_t) strtoull (optarg,
 189             /* endptr = */ NULL,
 190             /* base   = */ 0);
 191         if (errno != 0)
 192         {
 193           fprintf (stderr, "Parsing integer argument failed: %s\n",
 194               strerror (errno));
 195           exit_usage (argv[0], EXIT_FAILURE);
 196         }
 197         break;
 198       }
 199
 200       case 'h':
 201       default:
 202         exit_usage (argv[0], EXIT_SUCCESS);
 203     }
 204   }
 205
 206   return (0);
 207 } /* int read_options */
 208
 209 static sn_network_t *get_next (sn_network_t *n)
 210 {
 211   sn_network_t *nleft;
 212   sn_network_t *nright;
 213   sn_network_t *nret;
 214
 215   if (n == NULL)
 216     return (NULL);
 217
 218   nleft = sn_network_clone (n);
 219   nright = sn_network_clone (n);
 220
 221   assert (nleft != NULL);
 222   assert (nright != NULL);
 223
 224   /* combine the two parents */
 225   nret = sn_network_combine (nleft, nright);
 226
 227   sn_network_destroy (nleft);
 228   sn_network_destroy (nright);
 229
 230   /* randomly chose an input and do a min- or max-cut. */
 231   while (SN_NETWORK_INPUT_NUM (nret) > inputs_num)
 232   {
 233     int pos;
 234     enum sn_network_cut_dir_e dir;
 235
 236     pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (nret) - 1);
 237     dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
 238
 239     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (nret)));
 240
 241     sn_network_cut_at (nret, pos, dir);
 242   }
 243
 244   /* Make sure one network is always represented in the same way. */
 245   sn_network_unify (nret);
 246
 247   assert (SN_NETWORK_INPUT_NUM (nret) == inputs_num);
 248   return (nret);
 249 } /* sn_network_t *get_next */
 250
 251 static void random_walk (sn_network_t *n)
 252 {
 253   uint64_t iteration_counter = 0;
 254
 255   while (do_loop)
 256   {
 257     sn_network_t *next = get_next (n);
 258
 259     if (next == NULL)
 260     {
 261       fprintf (stderr, "get_next() failed.\n");
 262       return;
 263     }
 264
 265     account_network (next, iteration_counter);
 266
 267     if (do_output_network)
 268     {
 269       output_network (next);
 270       do_output_network = 0;
 271     }
 272
 273     sn_network_destroy (n);
 274     n = next;
 275     iteration_counter++;
 276
 277     if ((max_iterations > 0) && (iteration_counter >= max_iterations))
 278       break;
 279   } /* while (do_loop) */
 280
 281   sn_network_destroy (n);
 282
 283   printf ("# Exiting after %"PRIu64" iterations.\n", iteration_counter);
 284 } /* void random_walk */
 285
 286 int main (int argc, char **argv)
 287 {
 288   sn_network_t *start_network;
 289
 290   struct sigaction sigint_action;
 291   struct sigaction sigterm_action;
 292   struct sigaction sighup_action;
 293
 294   read_options (argc, argv);
 295   if (initial_input_file == NULL)
 296     exit_usage (argv[0], EXIT_FAILURE);
 297
 298   memset (&sigint_action, 0, sizeof (sigint_action));
 299   sigint_action.sa_handler = sigint_handler;
 300   sigaction (SIGINT, &sigint_action, NULL);
 301
 302   memset (&sigterm_action, '\0', sizeof (sigterm_action));
 303   sigterm_action.sa_handler = sigint_handler;
 304   sigaction (SIGTERM, &sigterm_action, NULL);
 305
 306   memset (&sighup_action, 0, sizeof (sighup_action));
 307   sighup_action.sa_handler = sighup_handler;
 308   sigaction (SIGHUP, &sighup_action, NULL);
 309
 310   all_networks = g_tree_new (compare_hashval);
 311   if (all_networks == NULL)
 312   {
 313     fprintf (stderr, "g_tree_new() failed.\n");
 314     exit (EXIT_FAILURE);
 315   }
 316
 317   start_network = sn_network_read_file (initial_input_file);
 318   if (start_network == NULL)
 319   {
 320     printf ("start_network == NULL\n");
 321     exit (EXIT_FAILURE);
 322   }
 323
 324   inputs_num = SN_NETWORK_INPUT_NUM(start_network);
 325
 326   random_walk (start_network);
 327   start_network = NULL;
 328
 329   printf ("# %"PRIu64" cycles were detected.\n", cycles_num);
 330
 331   exit (EXIT_SUCCESS);
 332   return (0);
 333 } /* int main */
 334
 335 /* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */