2 * libsortnetwork - src/sn-markov.c
3 * Copyright (C) 2008-2010 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
44 #include "sn_network.h"
45 #include "sn_random.h"
46 #include "histogram.h"
48 #if !defined(__GNUC__) || !__GNUC__
49 # define __attribute__(x) /**/
52 static int inputs_num = 16;
53 static _Bool use_bitonic = 0;
55 static char *initial_input_file = NULL;
56 static char *best_output_file = NULL;
58 static sn_network_t *best_solution = NULL;
59 static int best_rating = INT_MAX;
61 static _Bool do_loop = 1;
62 static uint64_t max_iterations = 0;
64 static histogram_t *histogram;
66 static void sigint_handler (int signal __attribute__((unused)))
69 } /* void sigint_handler */
71 static void exit_usage (const char *name, int status)
73 printf ("Usage: %s [options]\n"
75 "Valid options are:\n"
76 " -i <file> Initial input file (REQUIRED)\n"
77 " -o <file> Write the current best solution to <file>\n"
78 " -n <number> Maximum number of steps (iterations) to perform\n"
79 " -b Use the bitonic merger instead of the odd-even merger\n"
80 " -h Display usage information (this message)\n"
84 } /* void exit_usage */
86 int read_options (int argc, char **argv)
90 while ((option = getopt (argc, argv, "i:o:n:bh")) != -1)
96 if (initial_input_file != NULL)
97 free (initial_input_file);
98 initial_input_file = strdup (optarg);
104 if (best_output_file != NULL)
105 free (best_output_file);
106 best_output_file = strdup (optarg);
113 max_iterations = (uint64_t) strtoull (optarg,
118 fprintf (stderr, "Parsing integer argument failed: %s\n",
120 exit_usage (argv[0], EXIT_FAILURE);
131 exit_usage (argv[0], EXIT_SUCCESS);
136 } /* int read_options */
138 static int rate_network (const sn_network_t *n)
142 rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
143 rate += sn_network_get_comparator_num (n);
146 } /* int rate_network */
148 static sn_network_t *get_next (sn_network_t *n)
151 sn_network_t *nright;
157 nleft = sn_network_clone (n);
158 nright = sn_network_clone (n);
160 assert (nleft != NULL);
161 assert (nright != NULL);
163 /* combine the two parents */
165 nret = sn_network_combine_bitonic_merge (nleft, nright);
167 nret = sn_network_combine_odd_even_merge (nleft, nright);
169 sn_network_destroy (nleft);
170 sn_network_destroy (nright);
172 /* randomly chose an input and do a min- or max-cut. */
173 while (SN_NETWORK_INPUT_NUM (nret) > inputs_num)
176 enum sn_network_cut_dir_e dir;
178 pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (nret) - 1);
179 dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
181 assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (nret)));
183 sn_network_cut_at (nret, pos, dir);
186 /* compress the network to get a compact representation */
187 sn_network_compress (nret);
189 assert (SN_NETWORK_INPUT_NUM (nret) == inputs_num);
191 } /* sn_network_t *get_next */
193 static void random_walk (sn_network_t *n)
195 uint64_t iteration_counter = 0;
199 sn_network_t *next = get_next (n);
204 fprintf (stderr, "get_next() failed.\n");
208 rating = rate_network (next);
209 if (rating < best_rating)
211 printf ("New best rating (%i) after %"PRIu64" iterations.\n",
212 rating, iteration_counter);
214 best_rating = rating;
215 sn_network_destroy (best_solution);
216 best_solution = sn_network_clone (next);
219 hist_account (histogram, sn_network_get_comparator_num (next));
221 sn_network_destroy (n);
225 if ((max_iterations > 0) && (iteration_counter >= max_iterations))
227 } /* while (do_loop) */
229 sn_network_destroy (n);
231 printf ("Exiting after %"PRIu64" iterations.\n", iteration_counter);
232 } /* void random_walk */
234 int main (int argc, char **argv)
236 sn_network_t *start_network;
238 struct sigaction sigint_action;
239 struct sigaction sigterm_action;
241 histogram = hist_create ();
243 read_options (argc, argv);
244 if (initial_input_file == NULL)
245 exit_usage (argv[0], EXIT_FAILURE);
247 memset (&sigint_action, '\0', sizeof (sigint_action));
248 sigint_action.sa_handler = sigint_handler;
249 sigaction (SIGINT, &sigint_action, NULL);
251 memset (&sigterm_action, '\0', sizeof (sigterm_action));
252 sigterm_action.sa_handler = sigint_handler;
253 sigaction (SIGTERM, &sigterm_action, NULL);
255 start_network = sn_network_read_file (initial_input_file);
256 if (start_network == NULL)
258 printf ("start_network == NULL\n");
262 inputs_num = SN_NETWORK_INPUT_NUM(start_network);
264 printf ("Current configuration:\n"
265 " Initial network: %s\n"
266 " Number of inputs: %3i\n"
267 "=======================\n",
268 initial_input_file, inputs_num);
270 random_walk (start_network);
271 start_network = NULL;
273 hist_print (histogram);
274 hist_destroy (histogram);
277 if (best_solution != NULL)
279 if (best_output_file != NULL)
280 sn_network_write_file (best_solution, best_output_file);
282 printf ("=== Best solution (rating: %i) ===\n", best_rating);
283 sn_network_normalize (best_solution);
284 sn_network_show (best_solution);
285 sn_network_destroy (best_solution);
292 /* vim: set shiftwidth=2 softtabstop=2 : */