sn-count-markov: Add tool to determine the circle length of random walks.
authorFlorian Forster <octo@leeloo.octo.it>
Mon, 24 Jan 2011 06:42:08 +0000 (07:42 +0100)
committerFlorian Forster <octo@leeloo.octo.it>
Mon, 24 Jan 2011 06:42:08 +0000 (07:42 +0100)
README
configure.ac
src/Makefile.am
src/sn-count-markov.c [new file with mode: 0644]

diff --git a/README b/README
index 1cfdbbf..c5dfe69 100644 (file)
--- 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
index d8502fa..11b9f59 100644 (file)
@@ -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
 
index d433065..6d579fd 100644 (file)
@@ -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 (file)
index 0000000..698ca4d
--- /dev/null
@@ -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 <ff at octo.it>
+ **/
+
+#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 <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <string.h>
+
+#include <unistd.h>
+#include <signal.h>
+#include <assert.h>
+#include <limits.h>
+#include <errno.h>
+
+#include <glib.h>
+
+#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 <file>     Initial input file (REQUIRED)\n"
+      "  -o <file>     Write the current best solution to <file>\n"
+      "  -n <number>   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 : */