2 * libsortnetwork - src/sn-count-markov.c
3 * Copyright (C) 2008-2011 Florian octo Forster
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.
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.
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
19 * Florian octo Forster <ff at octo.it>
22 #ifndef _ISOC99_SOURCE
23 # define _ISOC99_SOURCE
25 #ifndef _POSIX_C_SOURCE
26 # define _POSIX_C_SOURCE 200809L
29 # define _XOPEN_SOURCE 700
46 #include "sn_network.h"
47 #include "sn_random.h"
49 #if !defined(__GNUC__) || !__GNUC__
50 # define __attribute__(x) /**/
53 static int inputs_num = 16;
55 static char *initial_input_file = NULL;
57 static GTree *all_networks = NULL;
58 static uint64_t cycles_num = 0;
60 static _Bool do_loop = 1;
61 static _Bool do_output_network = 0;
62 static uint64_t max_iterations = 0;
64 static void sigint_handler (__attribute__((unused)) int signal) /* {{{ */
67 } /* }}} void sigint_handler */
69 static void sighup_handler (__attribute__((unused)) int signal) /* {{{ */
71 do_output_network = 1;
72 } /* }}} void sighup_handler */
74 static int output_network (sn_network_t *n) /* {{{ */
81 fh = fopen ("/dev/tty", "w");
85 sn_network_show_fh (n, fh);
89 } /* }}} int output_network */
91 static gint compare_hashval (gconstpointer p0, gconstpointer p1) /* {{{ */
93 const uint64_t *i0 = (gconstpointer) p0;
94 const uint64_t *i1 = (gconstpointer) p1;
98 else if ((*i0) > (*i1))
102 } /* }}} gint account_network_compare */
104 static int account_network (const sn_network_t *n, uint64_t iteration) /* {{{ */
115 printf ("# prev_iter this_iter cyclelength hashval\n");
119 key = sn_network_get_hashval (n);
122 value_ptr = (uint64_t *) g_tree_lookup (all_networks, (gconstpointer) key_ptr);
123 if (value_ptr != NULL)
125 uint64_t cycle_length = iteration - (*value_ptr);
126 printf ("%"PRIu64" %"PRIu64" %"PRIu64" 0x%016"PRIx64"\n",
127 (*value_ptr), iteration, cycle_length, key);
131 *value_ptr = iteration;
138 key_ptr = malloc (sizeof (*key_ptr));
143 value_ptr = malloc (sizeof (*value_ptr));
144 if (value_ptr == NULL)
149 *value_ptr = iteration;
151 g_tree_insert (all_networks, (gpointer) key_ptr, (gpointer) value_ptr);
153 } /* }}} int account_network */
155 static void exit_usage (const char *name, int status)
157 printf ("Usage: %s [options]\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"
167 } /* void exit_usage */
169 int read_options (int argc, char **argv)
173 while ((option = getopt (argc, argv, "i:o:n:h")) != -1)
179 if (initial_input_file != NULL)
180 free (initial_input_file);
181 initial_input_file = strdup (optarg);
188 max_iterations = (uint64_t) strtoull (optarg,
193 fprintf (stderr, "Parsing integer argument failed: %s\n",
195 exit_usage (argv[0], EXIT_FAILURE);
202 exit_usage (argv[0], EXIT_SUCCESS);
207 } /* int read_options */
209 static sn_network_t *get_next (sn_network_t *n)
212 sn_network_t *nright;
218 nleft = sn_network_clone (n);
219 nright = sn_network_clone (n);
221 assert (nleft != NULL);
222 assert (nright != NULL);
224 /* combine the two parents */
225 nret = sn_network_combine (nleft, nright);
227 sn_network_destroy (nleft);
228 sn_network_destroy (nright);
230 /* randomly chose an input and do a min- or max-cut. */
231 while (SN_NETWORK_INPUT_NUM (nret) > inputs_num)
234 enum sn_network_cut_dir_e dir;
236 pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (nret) - 1);
237 dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
239 assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (nret)));
241 sn_network_cut_at (nret, pos, dir);
244 /* Make sure one network is always represented in the same way. */
245 sn_network_unify (nret);
247 assert (SN_NETWORK_INPUT_NUM (nret) == inputs_num);
249 } /* sn_network_t *get_next */
251 static void random_walk (sn_network_t *n)
253 uint64_t iteration_counter = 0;
257 sn_network_t *next = get_next (n);
261 fprintf (stderr, "get_next() failed.\n");
265 account_network (next, iteration_counter);
267 if (do_output_network)
269 output_network (next);
270 do_output_network = 0;
273 sn_network_destroy (n);
277 if ((max_iterations > 0) && (iteration_counter >= max_iterations))
279 } /* while (do_loop) */
281 sn_network_destroy (n);
283 printf ("# Exiting after %"PRIu64" iterations.\n", iteration_counter);
284 } /* void random_walk */
286 int main (int argc, char **argv)
288 sn_network_t *start_network;
290 struct sigaction sigint_action;
291 struct sigaction sigterm_action;
292 struct sigaction sighup_action;
294 read_options (argc, argv);
295 if (initial_input_file == NULL)
296 exit_usage (argv[0], EXIT_FAILURE);
298 memset (&sigint_action, 0, sizeof (sigint_action));
299 sigint_action.sa_handler = sigint_handler;
300 sigaction (SIGINT, &sigint_action, NULL);
302 memset (&sigterm_action, '\0', sizeof (sigterm_action));
303 sigterm_action.sa_handler = sigint_handler;
304 sigaction (SIGTERM, &sigterm_action, NULL);
306 memset (&sighup_action, 0, sizeof (sighup_action));
307 sighup_action.sa_handler = sighup_handler;
308 sigaction (SIGHUP, &sighup_action, NULL);
310 all_networks = g_tree_new (compare_hashval);
311 if (all_networks == NULL)
313 fprintf (stderr, "g_tree_new() failed.\n");
317 start_network = sn_network_read_file (initial_input_file);
318 if (start_network == NULL)
320 printf ("start_network == NULL\n");
324 inputs_num = SN_NETWORK_INPUT_NUM(start_network);
326 random_walk (start_network);
327 start_network = NULL;
329 printf ("# %"PRIu64" cycles were detected.\n", cycles_num);
335 /* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */