src/sn-count-cuts.c

   1 /**
   2  * libsortnetwork - src/sn-count-cuts.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 #include "config.h"
  23
  24 #include <stdlib.h>
  25 #include <stdio.h>
  26 #include <string.h>
  27 #include <unistd.h>
  28 #include <errno.h>
  29 #include <assert.h>
  30 #include <math.h>
  31
  32 #include "sn_network.h"
  33 #include "sn_random.h"
  34 #include "sn_hashtable.h"
  35
  36 static int cuts_num = 0;
  37 static uint64_t iterations_num = 1000000;
  38 static char *input_file = NULL;
  39
  40 static sn_hashtable_t *hashtable;
  41
  42 static double possible_cuts (int inputs_num) /* {{{ */
  43 {
  44   double n = (double) inputs_num;
  45   double k = (double) cuts_num;
  46
  47   double tmp = lgamma (1.0 + n)
  48     - (lgamma (1.0 + k) + lgamma (1.0 + n - k));
  49
  50   return (pow (2.0, k) * exp (tmp));
  51 } /* }}} double possible_cuts */
  52
  53 static double estimate_reachable_networks (sn_network_t *n) /* {{{ */
  54 {
  55   double cuts = possible_cuts (SN_NETWORK_INPUT_NUM (n));
  56   double pct = sn_hashtable_get_networks_pct (hashtable) / 100.0;
  57
  58   return (cuts * pct);
  59 } /* }}} double estimate_reachable_networks */
  60
  61 static void exit_usage (void) /* {{{ */
  62 {
  63   printf ("sn-count-cuts [options] <file0> <file1>\n"
  64       "\n"
  65       "Options:\n"
  66       "  -c        Number of cuts to perform.\n"
  67       "  -n        Maximum number of cuts to perform.\n"
  68       "  -h        Display this help and exit.\n"
  69       "\n");
  70   exit (EXIT_FAILURE);
  71 } /* }}} void exit_usage */
  72
  73 static int read_options (int argc, char **argv) /* {{{ */
  74 {
  75   int option;
  76
  77   while ((option = getopt (argc, argv, "c:n:h")) != -1)
  78   {
  79     switch (option)
  80     {
  81       case 'c':
  82       {
  83         int tmp = atoi (optarg);
  84         if (tmp <= 0)
  85         {
  86           fprintf (stderr, "Not a valid number of cuts: %s\n", optarg);
  87           exit_usage ();
  88         }
  89         cuts_num = tmp;
  90       }
  91       break;
  92
  93       case 'n':
  94       {
  95         uint64_t tmp = (uint64_t) strtoull (optarg, /* endptr = */ NULL, /* base = */ 10);
  96         if (tmp <= 0)
  97         {
  98           fprintf (stderr, "Not a valid number of iterations: %s\n", optarg);
  99           exit_usage ();
 100         }
 101         iterations_num = tmp;
 102       }
 103       break;
 104
 105       case 'h':
 106       default:
 107         exit_usage ();
 108     }
 109   }
 110
 111   if ((argc - optind) >= 1)
 112     input_file = argv[optind];
 113
 114   return (0);
 115 } /* }}} int read_options */
 116
 117 static int create_random_cut (const sn_network_t *n) /* {{{ */
 118 {
 119   sn_network_t *n_copy;
 120   int mask[SN_NETWORK_INPUT_NUM (n)];
 121   int cuts_left = cuts_num;
 122   int status;
 123
 124   memset (mask, 0, sizeof (mask));
 125   while (cuts_left > 0)
 126   {
 127     int input = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n));
 128
 129     if (mask[input] != 0)
 130       continue;
 131
 132     mask[input] = (2 * sn_bounded_random (0, 1)) - 1;
 133     cuts_left--;
 134   }
 135
 136   n_copy = sn_network_clone (n);
 137   if (n_copy == NULL)
 138     return (ENOMEM);
 139
 140   status = sn_network_cut (n_copy, mask);
 141   if (status != 0)
 142   {
 143     sn_network_destroy (n_copy);
 144     return (status);
 145   }
 146
 147   sn_network_unify (n_copy);
 148
 149   sn_hashtable_account (hashtable, n_copy);
 150
 151   sn_network_destroy (n_copy);
 152   return (0);
 153 } /* }}} int create_random_cut */
 154
 155 static int print_stats (sn_network_t *n) /* {{{ */
 156 {
 157   static _Bool first_call = 1;
 158
 159   if (first_call)
 160   {
 161     printf ("# iterations unique collisions estimate\n");
 162     first_call = 0;
 163   }
 164
 165   printf ("%"PRIu64" %"PRIu64" %"PRIu64" %.0f\n",
 166       sn_hashtable_get_total (hashtable),
 167       sn_hashtable_get_networks (hashtable),
 168       sn_hashtable_get_collisions (hashtable),
 169       estimate_reachable_networks (n));
 170
 171   return (0);
 172 } /* }}} int print_stats */
 173
 174 int main (int argc, char **argv) /* {{{ */
 175 {
 176   sn_network_t *n;
 177   uint64_t i;
 178
 179   read_options (argc, argv);
 180
 181   if ((input_file == NULL)
 182       || (strcmp ("-", input_file) == 0))
 183     n = sn_network_read (stdin);
 184   else
 185     n = sn_network_read_file (input_file);
 186   if (n == NULL)
 187   {
 188     fprintf (stderr, "Unable to read network.\n");
 189     exit (EXIT_FAILURE);
 190   }
 191
 192   if (cuts_num <= 0)
 193     cuts_num = SN_NETWORK_INPUT_NUM (n) / 2;
 194
 195   hashtable = sn_hashtable_create ();
 196   if (hashtable == NULL)
 197     exit (EXIT_FAILURE);
 198
 199   for (i = 0; i < iterations_num; i++)
 200   {
 201     create_random_cut (n);
 202
 203     if ((i < 100)
 204         || ((i < 1000) && (((i + 1) % 10) == 0))
 205         || ((i < 10000) && (((i + 1) % 100) == 0))
 206         || ((i < 100000) && (((i + 1) % 1000) == 0))
 207         || ((i < 1000000) && (((i + 1) % 10000) == 0))
 208         || ((i < 10000000) && (((i + 1) % 100000) == 0)))
 209       print_stats (n);
 210   }
 211
 212   if (((i - 1) < 100)
 213       || (((i - 1) < 1000) && ((i % 10) == 0))
 214       || (((i - 1) < 10000) && ((i % 100) == 0))
 215       || (((i - 1) < 100000) && ((i % 1000) == 0))
 216       || (((i - 1) < 1000000) && ((i % 10000) == 0))
 217       || (((i - 1) < 10000000) && ((i % 100000) == 0)))
 218   {
 219     /* do nothing */
 220   }
 221   else
 222   {
 223     print_stats (n);
 224   }
 225
 226   return (0);
 227 } /* }}} int main */
 228
 229 /* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */