From 48c59e57e010d13aeba74ff02257127493377b5e Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Mon, 24 Jan 2011 07:42:08 +0100 Subject: [PATCH] sn-count-markov: Add tool to determine the circle length of random walks. --- README | 2 + configure.ac | 5 + src/Makefile.am | 6 +- src/sn-count-markov.c | 293 ++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 305 insertions(+), 1 deletion(-) create mode 100644 src/sn-count-markov.c diff --git a/README b/README index 1cfdbbf..c5dfe69 100644 --- a/README +++ b/README @@ -83,6 +83,8 @@ Experimental / research applications: * sn-bb * sn-bb-merge + * sn-count-cuts + * sn-count-markov * sn-markov * sn-evolution * sn-evolution2 diff --git a/configure.ac b/configure.ac index d8502fa..11b9f59 100644 --- a/configure.ac +++ b/configure.ac @@ -14,6 +14,7 @@ AC_PROG_INSTALL AM_PROG_CC_C_O AC_DISABLE_STATIC AC_PROG_LIBTOOL +PKG_PROG_PKG_CONFIG # Libtool stuff LT_INIT @@ -108,6 +109,10 @@ AC_SUBST(LIBPOPULATION_LIBS) AM_CONDITIONAL(BUILD_WITH_LIBPOPULATION, test "x$with_libpopulation" = "xyes") # }}} --with-libpopulation +PKG_CHECK_MODULES([glib], [glib-2.0], + [have_libglib="yes"], + [have_libglib="no"]) + AC_CONFIG_FILES([Makefile src/Makefile]) AC_OUTPUT diff --git a/src/Makefile.am b/src/Makefile.am index d433065..6d579fd 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -5,7 +5,7 @@ lib_LTLIBRARIES = libsortnetwork.la bin_PROGRAMS = sn-apply \ sn-bitonicmerge sn-bitonicsort \ sn-bb sn-bb-merge sn-check-bf \ - sn-count-cuts sn-cut \ + sn-count-cuts sn-count-markov 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 @@ -39,6 +39,10 @@ sn_check_bf_LDADD = libsortnetwork.la sn_count_cuts_SOURCES = sn-count-cuts.c sn_count_cuts_LDADD = libsortnetwork.la -lm +sn_count_markov_SOURCES = sn-count-markov.c +sn_count_markov_CFLAGS = $(AM_CFLAGS) $(glib_CFLAGS) +sn_count_markov_LDADD = libsortnetwork.la $(glib_LIBS) + sn_cut_SOURCES = sn-cut.c sn_cut_LDADD = libsortnetwork.la diff --git a/src/sn-count-markov.c b/src/sn-count-markov.c new file mode 100644 index 0000000..698ca4d --- /dev/null +++ b/src/sn-count-markov.c @@ -0,0 +1,293 @@ +/** + * libsortnetwork - src/sn-count-markov.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 + **/ + +#ifndef _ISOC99_SOURCE +# define _ISOC99_SOURCE +#endif +#ifndef _POSIX_C_SOURCE +# define _POSIX_C_SOURCE 200809L +#endif +#ifndef _XOPEN_SOURCE +# define _XOPEN_SOURCE 700 +#endif + +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include + +#include + +#include "sn_network.h" +#include "sn_random.h" + +#if !defined(__GNUC__) || !__GNUC__ +# define __attribute__(x) /**/ +#endif + +static int inputs_num = 16; + +static char *initial_input_file = NULL; + +static GTree *all_networks = NULL; +static uint64_t cycles_num = 0; + +static _Bool do_loop = 1; +static uint64_t max_iterations = 0; + +static void sigint_handler (int signal __attribute__((unused))) +{ + do_loop = 0; +} /* void sigint_handler */ + +static gint compare_hashval (gconstpointer p0, gconstpointer p1) /* {{{ */ +{ + const uint64_t *i0 = (gconstpointer) p0; + const uint64_t *i1 = (gconstpointer) p1; + + if ((*i0) < (*i1)) + return (-1); + else if ((*i0) > (*i1)) + return (1); + else + return (0); +} /* }}} gint account_network_compare */ + +static int account_network (const sn_network_t *n, uint64_t iteration) /* {{{ */ +{ + uint64_t key; + uint64_t *key_ptr; + uint64_t *value_ptr; + + if (n == NULL) + return (EINVAL); + + if (iteration == 0) + printf ("# iteration cyclelength\n"); + + key = sn_network_get_hashval (n); + key_ptr = &key; + + value_ptr = (uint64_t *) g_tree_lookup (all_networks, (gconstpointer) key_ptr); + if (value_ptr != NULL) + { + uint64_t cycle_length = iteration - (*value_ptr); + printf ("%"PRIu64" %"PRIu64"\n", iteration, cycle_length); + + cycles_num++; + *value_ptr = iteration; + return (0); + } + + key_ptr = malloc (sizeof (*key_ptr)); + if (key_ptr == NULL) + return (ENOMEM); + *key_ptr = key; + + value_ptr = malloc (sizeof (*value_ptr)); + if (value_ptr == NULL) + { + free (key_ptr); + return (ENOMEM); + } + *value_ptr = iteration; + + g_tree_insert (all_networks, (gpointer) key_ptr, (gpointer) value_ptr); + return (0); +} /* }}} int account_network */ + +static void exit_usage (const char *name, int status) +{ + printf ("Usage: %s [options]\n" + "\n" + "Valid options are:\n" + " -i Initial input file (REQUIRED)\n" + " -o Write the current best solution to \n" + " -n Maximum number of steps (iterations) to perform\n" + " -h Display usage information (this message)\n" + "\n", + name); + exit (status); +} /* void exit_usage */ + +int read_options (int argc, char **argv) +{ + int option; + + while ((option = getopt (argc, argv, "i:o:n:h")) != -1) + { + switch (option) + { + case 'i': + { + if (initial_input_file != NULL) + free (initial_input_file); + initial_input_file = strdup (optarg); + break; + } + + case 'n': + { + errno = 0; + max_iterations = (uint64_t) strtoull (optarg, + /* endptr = */ NULL, + /* base = */ 0); + if (errno != 0) + { + fprintf (stderr, "Parsing integer argument failed: %s\n", + strerror (errno)); + exit_usage (argv[0], EXIT_FAILURE); + } + break; + } + + case 'h': + default: + exit_usage (argv[0], EXIT_SUCCESS); + } + } + + return (0); +} /* int read_options */ + +static sn_network_t *get_next (sn_network_t *n) +{ + sn_network_t *nleft; + sn_network_t *nright; + sn_network_t *nret; + + if (n == NULL) + return (NULL); + + nleft = sn_network_clone (n); + nright = sn_network_clone (n); + + assert (nleft != NULL); + assert (nright != NULL); + + /* combine the two parents */ + nret = sn_network_combine (nleft, nright); + + sn_network_destroy (nleft); + sn_network_destroy (nright); + + /* randomly chose an input and do a min- or max-cut. */ + while (SN_NETWORK_INPUT_NUM (nret) > inputs_num) + { + int pos; + enum sn_network_cut_dir_e dir; + + pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (nret) - 1); + dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX; + + assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (nret))); + + sn_network_cut_at (nret, pos, dir); + } + + /* Make sure one network is always represented in the same way. */ + sn_network_unify (nret); + + assert (SN_NETWORK_INPUT_NUM (nret) == inputs_num); + return (nret); +} /* sn_network_t *get_next */ + +static void random_walk (sn_network_t *n) +{ + uint64_t iteration_counter = 0; + + while (do_loop) + { + sn_network_t *next = get_next (n); + + if (next == NULL) + { + fprintf (stderr, "get_next() failed.\n"); + return; + } + + account_network (next, iteration_counter); + + sn_network_destroy (n); + n = next; + iteration_counter++; + + if ((max_iterations > 0) && (iteration_counter >= max_iterations)) + break; + } /* while (do_loop) */ + + sn_network_destroy (n); + + printf ("# Exiting after %"PRIu64" iterations.\n", iteration_counter); +} /* void random_walk */ + +int main (int argc, char **argv) +{ + sn_network_t *start_network; + + struct sigaction sigint_action; + struct sigaction sigterm_action; + + read_options (argc, argv); + if (initial_input_file == NULL) + exit_usage (argv[0], EXIT_FAILURE); + + memset (&sigint_action, '\0', sizeof (sigint_action)); + sigint_action.sa_handler = sigint_handler; + sigaction (SIGINT, &sigint_action, NULL); + + memset (&sigterm_action, '\0', sizeof (sigterm_action)); + sigterm_action.sa_handler = sigint_handler; + sigaction (SIGTERM, &sigterm_action, NULL); + + all_networks = g_tree_new (compare_hashval); + if (all_networks == NULL) + { + fprintf (stderr, "g_tree_new() failed.\n"); + exit (EXIT_FAILURE); + } + + start_network = sn_network_read_file (initial_input_file); + if (start_network == NULL) + { + printf ("start_network == NULL\n"); + exit (EXIT_FAILURE); + } + + inputs_num = SN_NETWORK_INPUT_NUM(start_network); + + random_walk (start_network); + start_network = NULL; + + printf ("# %"PRIu64" cycles were detected.\n", cycles_num); + + exit (EXIT_SUCCESS); + return (0); +} /* int main */ + +/* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */ -- 2.11.0