From 3c95047d30f11d5c4167c3f1dc7d33fff8f6bcc0 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Mon, 10 Jan 2011 10:46:43 +0100 Subject: [PATCH] sn-tex-cut: Add tool to visualize cut sequences. --- README | 4 + src/Makefile.am | 5 +- src/sn-tex-cut.c | 448 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 456 insertions(+), 1 deletion(-) create mode 100644 src/sn-tex-cut.c diff --git a/README b/README index 552d6b9..1cfdbbf 100644 --- a/README +++ b/README @@ -75,6 +75,10 @@ The distribution includes the following utility programs: Prints the TikZ / TeX sources of a graphic representation of a comparator network to STDOUT. + * sn-tex-cut + Prints the TikZ / TeX sources of a graphic representation of a cut sequence + to STDOUT. + Experimental / research applications: * sn-bb diff --git a/src/Makefile.am b/src/Makefile.am index 1924258..ae4e12f 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -7,7 +7,7 @@ bin_PROGRAMS = sn-apply \ sn-bb sn-bb-merge sn-check-bf 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-shmoo sn-show sn-svg sn-tex sn-tex-cut libsortnetwork_la_SOURCES = sn_network.c sn_network.h \ sn_stage.c sn_stage.h \ @@ -70,6 +70,9 @@ sn_svg_LDADD = libsortnetwork.la sn_tex_SOURCES = sn-tex.c sn_tex_LDADD = libsortnetwork.la +sn_tex_cut_SOURCES = sn-tex-cut.c +sn_tex_cut_LDADD = libsortnetwork.la + if BUILD_WITH_LIBPOPULATION bin_PROGRAMS += sn-evolution sn-evolution2 sn-evolution-cut sn-evolution-merge diff --git a/src/sn-tex-cut.c b/src/sn-tex-cut.c new file mode 100644 index 0000000..567e3c8 --- /dev/null +++ b/src/sn-tex-cut.c @@ -0,0 +1,448 @@ +/** + * libsortnetwork - src/sn-tex.c + * Copyright (C) 2008-2010 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" + +#ifndef _ISOC99_SOURCE +# define _ISOC99_SOURCE +#endif +#ifndef _POSIX_C_SOURCE +# define _POSIX_C_SOURCE 200112L +#endif + +#include +#include +#include +#include +#include +#include +#include + +#include "sn_network.h" + +const char *input_file = NULL; + +/* 21cm (DIN-A4) - 2x3cm Rand = 15cm */ +static double output_width = 15.0; +static double scale = 1.0; +static double inner_spacing = 0.3; +static double outer_spacing = 1.0; +static double vertical_spacing = 0.8; + +static double x_offset; +static int next_vertex_number = 0; + +static int *mask = NULL; + +#define INPUT_TO_Y(i) (((double) (i)) * vertical_spacing) + +static void exit_usage (void) /* {{{ */ +{ + printf ("Usage: sn-tex-cut [options] [:min|max] [[:min|max] ...]\n" + "\n" + "Valid options are:\n" + " -i Read comparator network from file.\n" + " -w Specify the width of the graph (in TikZ default units).\n" + "\n"); + exit (EXIT_FAILURE); +} /* }}} void exit_usage */ + +static int read_options (int argc, char **argv) /* {{{ */ +{ + int option; + + while ((option = getopt (argc, argv, "w:i:h?")) != -1) + { + switch (option) + { + case 'w': + { + double width = atof (optarg); + if (width <= 0.0) + { + fprintf (stderr, "Invalid width argument: %s\n", optarg); + exit (EXIT_FAILURE); + } + output_width = width; + break; + } + + case 'i': + input_file = optarg; + break; + + case 'h': + case '?': + default: + exit_usage (); + } + } + + return (0); +} /* }}} int read_options */ + +static int read_mask (sn_network_t *n, int argc, char **argv) /* {{{ */ +{ + int i; + + mask = calloc (SN_NETWORK_INPUT_NUM (n), sizeof (*mask)); + if (mask == NULL) + return (ENOMEM); + + for (i = 0; i < argc; i++) + { + char *endptr = NULL; + int pos; + int val = 1; + + pos = (int) strtol (argv[i], &endptr, /* base = */ 0); + if (strcasecmp (":min", endptr) == 0) + val = -1; + + if ((pos < 0) || (pos >= SN_NETWORK_INPUT_NUM (n))) + { + fprintf (stderr, "Invalid line number: %i\n", pos); + return (-1); + } + + mask[pos] = val; + } + + return (0); +} /* }}} int read_mask */ + +static double determine_stage_width (sn_stage_t *s) /* {{{ */ +{ + int lines[s->comparators_num]; + int right[s->comparators_num]; + int lines_used = 0; + int i; + + if (SN_STAGE_COMP_NUM (s) == 0) + return (0.0); + + for (i = 0; i < SN_STAGE_COMP_NUM (s); i++) + { + lines[i] = -1; + right[i] = -1; + } + + for (i = 0; i < SN_STAGE_COMP_NUM (s); i++) + { + int j; + sn_comparator_t *c = SN_STAGE_COMP_GET (s, i); + + for (j = 0; j < lines_used; j++) + if (SN_COMP_LEFT (c) > right[j]) + break; + + lines[i] = j; + right[j] = SN_COMP_RIGHT (c); + if (j >= lines_used) + lines_used = j + 1; + } + assert (lines_used >= 1); + + return (((double) (lines_used - 1)) * inner_spacing); +} /* }}} double determine_stage_width */ + +static double determine_network_width (sn_network_t *n) /* {{{ */ +{ + double width; + int i; + + /* Spacing between stages and at the beginning and end of the network */ + width = (SN_NETWORK_STAGE_NUM (n) + 1) * outer_spacing; + + /* Spacing required within a stage */ + for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++) + width += determine_stage_width (SN_NETWORK_STAGE_GET (n, i)); + + return (width); +} /* }}} double determine_network_width */ + +static int stage_print_lines (sn_stage_t *s, int *mask, double *x_left) /* {{{ */ +{ + int lines[s->comparators_num]; + int right[s->comparators_num]; + int lines_used = 0; + int i; + + for (i = 0; i < s->comparators_num; i++) + { + lines[i] = -1; + right[i] = -1; + } + + for (i = 0; i < s->comparators_num; i++) + { + int j; + sn_comparator_t *c = s->comparators + i; + double x_right; + int comp_left; + int comp_right; + int mask_left; + int mask_right; + const char *left_class = "edge"; + const char *right_class = "edge"; + + comp_left = SN_COMP_LEFT (c); + comp_right = SN_COMP_RIGHT (c); + + mask_left = mask[comp_left]; + mask_right = mask[comp_right]; + + for (j = 0; j < lines_used; j++) + if (comp_left > right[j]) + break; + + lines[i] = j; + right[j] = comp_right; + if (j >= lines_used) + lines_used = j + 1; + + if ((mask_left == mask_right) + || ((mask_left <= 0) && (mask_right >= 0))) + continue; + + if (mask_left > 0) + left_class = "edge maximum"; + if (mask_right < 0) + right_class = "edge minimum"; + + x_right = x_offset + (j * inner_spacing); + + printf ("\\path[%s] (%.2f,%.2f) -- (%.2f,%.2f);\n", + left_class, + x_left[comp_left], INPUT_TO_Y (comp_left), + x_right, INPUT_TO_Y (comp_left)); + printf ("\\path[%s] (%.2f,%.2f) -- (%.2f,%.2f);\n", + right_class, + x_left[comp_right], INPUT_TO_Y (comp_right), + x_right, INPUT_TO_Y (comp_right)); + + x_left[comp_left] = x_right; + x_left[comp_right] = x_right; + } + + x_offset = x_offset + ((lines_used - 1) * inner_spacing) + outer_spacing; + + return (0); +} /* }}} int stage_print_lines */ + +static int network_print_lines (sn_network_t *n, int *mask_orig) /* {{{ */ +{ + int mask[SN_NETWORK_INPUT_NUM (n)]; + double x_left[SN_NETWORK_INPUT_NUM (n)]; + int i; + + memcpy (mask, mask_orig, sizeof (mask)); + for (i = 0; i < SN_NETWORK_INPUT_NUM (n); i++) + x_left[i] = 0.0; + + x_offset = outer_spacing; + for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++) + { + stage_print_lines (SN_NETWORK_STAGE_GET (n, i), mask, x_left); + sn_stage_sort (SN_NETWORK_STAGE_GET (n, i), mask); + } + + for (i = 0; i < SN_NETWORK_INPUT_NUM (n); i++) + { + const char *class = "edge"; + + if (mask[i] < 0) + class = "edge minimum"; + else if (mask[i] > 0) + class = "edge maximum"; + + printf ("\\path[%s] (%.2f,%.2f) -- (%.2f,%.2f);\n", + class, + x_left[i], INPUT_TO_Y (i), + x_offset, INPUT_TO_Y (i)); + } + + return (0); +} /* }}} int network_print_lines */ + +static const char *mask_to_class (int left, int right, int *mask) /* {{{ */ +{ + if (mask[left] == mask[right]) + { + if (mask[left] == 0) + return (""); + else if (mask[left] > 0) + return (" inactive maximum"); + else + return (" inactive minimum"); + } + else if (mask[left] < mask[right]) + { + if ((mask[left] < 0) && (mask[right] > 0)) + return (" inactive minimum maximum"); + else if (mask[left] < 0) + return (" inactive minimum"); + else + return (" inactive maximum"); + } + else + { + const char *class; + int tmp; + + if ((mask[left] > 0) && (mask[right] < 0)) + class = " active minimum maximum"; + else if (mask[left] > 0) + class = " active maximum"; + else + class = " active minimum"; + + tmp = mask[left]; + mask[left] = mask[right]; + mask[right] = tmp; + + return (class); + } +} /* }}} const char *mask_to_class */ + +static int stage_print_comparators (sn_stage_t *s, int *mask) /* {{{ */ +{ + int lines[s->comparators_num]; + int right[s->comparators_num]; + int lines_used = 0; + int i; + + for (i = 0; i < s->comparators_num; i++) + { + lines[i] = -1; + right[i] = -1; + } + + for (i = 0; i < s->comparators_num; i++) + { + int j; + sn_comparator_t *c = s->comparators + i; + const char *class; + + int min_num; + int max_num; + + min_num = next_vertex_number; + next_vertex_number++; + + max_num = next_vertex_number; + next_vertex_number++; + + for (j = 0; j < lines_used; j++) + if (SN_COMP_LEFT (c) > right[j]) + break; + + lines[i] = j; + right[j] = SN_COMP_RIGHT (c); + if (j >= lines_used) + lines_used = j + 1; + + class = mask_to_class (SN_COMP_LEFT (c), SN_COMP_RIGHT (c), mask); + + printf ("\\node[vertex%s] (v%i) at (%.2f,%.2f) {};\n" + "\\node[vertex%s] (v%i) at (%.2f,%.2f) {};\n" + "\\path[comp%s] (v%i) -- (v%i);\n" + "\n", + class, min_num, x_offset + (j * inner_spacing), INPUT_TO_Y (c->min), + class, max_num, x_offset + (j * inner_spacing), INPUT_TO_Y (c->max), + class, min_num, max_num); + } + + x_offset = x_offset + ((lines_used - 1) * inner_spacing) + outer_spacing; + + return (0); +} /* }}} int stage_print_comparators */ + +static int network_print_comparators (sn_network_t *n, int *mask_orig) /* {{{ */ +{ + int mask[SN_NETWORK_INPUT_NUM (n)]; + int i; + + memcpy (mask, mask_orig, sizeof (mask)); + + x_offset = outer_spacing; + for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++) + stage_print_comparators (SN_NETWORK_STAGE_GET (n, i), mask); + + return (0); +} /* }}} int network_print_comparators */ + +int main (int argc, char **argv) /* {{{ */ +{ + sn_network_t *n; + FILE *fh = NULL; + double orig_width; + int status; + + read_options (argc, argv); + + if (input_file == NULL) + fh = stdin; + else + fh = fopen (input_file, "r"); + + if (fh == NULL) + exit_usage (); + + n = sn_network_read (fh); + if (n == NULL) + { + fprintf (stderr, "Unable to read network from file handle.\n"); + exit (EXIT_FAILURE); + } + + status = read_mask (n, argc - optind, argv + optind); + if (status != 0) + { + fprintf (stderr, "read_mask failed.\n"); + exit (EXIT_FAILURE); + } + assert (mask != NULL); + + orig_width = determine_network_width (n); + if (orig_width <= 0.0) + { + fprintf (stderr, "determine_network_width returned invalid value %g.\n", + orig_width); + exit (EXIT_FAILURE); + } + + scale = output_width / orig_width; + inner_spacing *= scale; + outer_spacing *= scale; + vertical_spacing *= scale; + + printf ("\\begin{tikzpicture}[auto]\n"); + + network_print_lines (n, mask); + network_print_comparators (n, mask); + + printf ("\\end{tikzpicture}\n"); + + return (0); +} /* }}} int main */ + +/* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */ -- 2.11.0