From bb13a18868f21a51259bb19e6f6127ce4d0a4a52 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Mon, 17 Jan 2011 10:50:21 +0100 Subject: [PATCH] sn-count-cuts: Tool to count the number of networks reachable through cuts. --- src/Makefile.am | 6 +- src/sn-count-cuts.c | 229 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 234 insertions(+), 1 deletion(-) create mode 100644 src/sn-count-cuts.c diff --git a/src/Makefile.am b/src/Makefile.am index 7306d6e..d433065 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -4,7 +4,8 @@ lib_LTLIBRARIES = libsortnetwork.la bin_PROGRAMS = sn-apply \ sn-bitonicmerge sn-bitonicsort \ - sn-bb sn-bb-merge sn-check-bf sn-cut \ + sn-bb sn-bb-merge sn-check-bf \ + sn-count-cuts sn-cut \ sn-info sn-markov sn-merge sn-normalize \ sn-oddevenmerge sn-oddevensort sn-pairwisesort \ sn-shmoo sn-show sn-svg sn-tex sn-tex-cut @@ -35,6 +36,9 @@ sn_bitonicsort_LDADD = libsortnetwork.la sn_check_bf_SOURCES = sn-check-bf.c sn_check_bf_LDADD = libsortnetwork.la +sn_count_cuts_SOURCES = sn-count-cuts.c +sn_count_cuts_LDADD = libsortnetwork.la -lm + sn_cut_SOURCES = sn-cut.c sn_cut_LDADD = libsortnetwork.la diff --git a/src/sn-count-cuts.c b/src/sn-count-cuts.c new file mode 100644 index 0000000..d6e13f9 --- /dev/null +++ b/src/sn-count-cuts.c @@ -0,0 +1,229 @@ +/** + * libsortnetwork - src/sn-count-cuts.c + * Copyright (C) 2008-2011 Florian octo Forster + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; only version 2 of the License is applicable. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: + * Florian octo Forster + **/ + +#include "config.h" + +#include +#include +#include +#include +#include +#include +#include + +#include "sn_network.h" +#include "sn_random.h" +#include "sn_hashtable.h" + +static int cuts_num = 0; +static uint64_t iterations_num = 1000000; +static char *input_file = NULL; + +static sn_hashtable_t *hashtable; + +static double possible_cuts (int inputs_num) /* {{{ */ +{ + double n = (double) inputs_num; + double k = (double) cuts_num; + + double tmp = lgamma (1.0 + n) + - (lgamma (1.0 + k) + lgamma (1.0 + n - k)); + + return (pow (2.0, k) * exp (tmp)); +} /* }}} double possible_cuts */ + +static double estimate_reachable_networks (sn_network_t *n) /* {{{ */ +{ + double cuts = possible_cuts (SN_NETWORK_INPUT_NUM (n)); + double pct = sn_hashtable_get_networks_pct (hashtable) / 100.0; + + return (cuts * pct); +} /* }}} double estimate_reachable_networks */ + +static void exit_usage (void) /* {{{ */ +{ + printf ("sn-count-cuts [options] \n" + "\n" + "Options:\n" + " -c Number of cuts to perform.\n" + " -n Maximum number of cuts to perform.\n" + " -h Display this help and exit.\n" + "\n"); + exit (EXIT_FAILURE); +} /* }}} void exit_usage */ + +static int read_options (int argc, char **argv) /* {{{ */ +{ + int option; + + while ((option = getopt (argc, argv, "c:n:h")) != -1) + { + switch (option) + { + case 'c': + { + int tmp = atoi (optarg); + if (tmp <= 0) + { + fprintf (stderr, "Not a valid number of cuts: %s\n", optarg); + exit_usage (); + } + cuts_num = tmp; + } + break; + + case 'n': + { + uint64_t tmp = (uint64_t) strtoull (optarg, /* endptr = */ NULL, /* base = */ 10); + if (tmp <= 0) + { + fprintf (stderr, "Not a valid number of iterations: %s\n", optarg); + exit_usage (); + } + iterations_num = tmp; + } + break; + + case 'h': + default: + exit_usage (); + } + } + + if ((argc - optind) >= 1) + input_file = argv[optind]; + + return (0); +} /* }}} int read_options */ + +static int create_random_cut (const sn_network_t *n) /* {{{ */ +{ + sn_network_t *n_copy; + int mask[SN_NETWORK_INPUT_NUM (n)]; + int cuts_left = cuts_num; + int status; + + memset (mask, 0, sizeof (mask)); + while (cuts_left > 0) + { + int input = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n)); + + if (mask[input] != 0) + continue; + + mask[input] = (2 * sn_bounded_random (0, 1)) - 1; + cuts_left--; + } + + n_copy = sn_network_clone (n); + if (n_copy == NULL) + return (ENOMEM); + + status = sn_network_cut (n_copy, mask); + if (status != 0) + { + sn_network_destroy (n_copy); + return (status); + } + + sn_network_unify (n_copy); + + sn_hashtable_account (hashtable, n_copy); + + sn_network_destroy (n_copy); + return (0); +} /* }}} int create_random_cut */ + +static int print_stats (sn_network_t *n) /* {{{ */ +{ + static _Bool first_call = 1; + + if (first_call) + { + printf ("# iterations unique collisions estimate\n"); + first_call = 0; + } + + printf ("%"PRIu64" %"PRIu64" %"PRIu64" %.0f\n", + sn_hashtable_get_total (hashtable), + sn_hashtable_get_networks (hashtable), + sn_hashtable_get_collisions (hashtable), + estimate_reachable_networks (n)); + + return (0); +} /* }}} int print_stats */ + +int main (int argc, char **argv) /* {{{ */ +{ + sn_network_t *n; + uint64_t i; + + read_options (argc, argv); + + if ((input_file == NULL) + || (strcmp ("-", input_file) == 0)) + n = sn_network_read (stdin); + else + n = sn_network_read_file (input_file); + if (n == NULL) + { + fprintf (stderr, "Unable to read network.\n"); + exit (EXIT_FAILURE); + } + + if (cuts_num <= 0) + cuts_num = SN_NETWORK_INPUT_NUM (n) / 2; + + hashtable = sn_hashtable_create (); + if (hashtable == NULL) + exit (EXIT_FAILURE); + + for (i = 0; i < iterations_num; i++) + { + create_random_cut (n); + + if ((i < 100) + || ((i < 1000) && (((i + 1) % 10) == 0)) + || ((i < 10000) && (((i + 1) % 100) == 0)) + || ((i < 100000) && (((i + 1) % 1000) == 0)) + || ((i < 1000000) && (((i + 1) % 10000) == 0)) + || ((i < 10000000) && (((i + 1) % 100000) == 0))) + print_stats (n); + } + + if (((i - 1) < 100) + || (((i - 1) < 1000) && ((i % 10) == 0)) + || (((i - 1) < 10000) && ((i % 100) == 0)) + || (((i - 1) < 100000) && ((i % 1000) == 0)) + || (((i - 1) < 1000000) && ((i % 10000) == 0)) + || (((i - 1) < 10000000) && ((i % 100000) == 0))) + { + /* do nothing */ + } + else + { + print_stats (n); + } + + return (0); +} /* }}} int main */ + +/* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */ -- 2.11.0