src/regex/regex_test_graph.c

   1 /*
   2      This file is part of GNUnet
   3      Copyright (C) 2012 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18      SPDX-License-Identifier: AGPL3.0-or-later
  19  */
  20 /**
  21  * @file src/regex/regex_test_graph.c
  22  * @brief functions for creating .dot graphs from regexes
  23  * @author Maximilian Szengel
  24  */
  25 #include "platform.h"
  26 #include "regex_internal_lib.h"
  27 #include "regex_test_lib.h"
  28 #include "regex_internal.h"
  29
  30 /**
  31  * Context for graph creation. Passed as the cls to
  32  * REGEX_TEST_automaton_save_graph_step.
  33  */
  34 struct REGEX_TEST_Graph_Context {
  35   /**
  36    * File pointer to the dot file used for output.
  37    */
  38   FILE *filep;
  39
  40   /**
  41    * Verbose flag, if it's set to GNUNET_YES additional info will be printed in
  42    * the graph.
  43    */
  44   int verbose;
  45
  46   /**
  47    * Coloring flag, if set to GNUNET_YES SCCs will be colored.
  48    */
  49   int coloring;
  50 };
  51
  52
  53 /**
  54  * Recursive function doing DFS with 'v' as a start, detecting all SCCs inside
  55  * the subgraph reachable from 'v'. Used with scc_tarjan function to detect all
  56  * SCCs inside an automaton.
  57  *
  58  * @param scc_counter counter for numbering the sccs
  59  * @param v start vertex
  60  * @param index current index
  61  * @param stack stack for saving all SCCs
  62  * @param stack_size current size of the stack
  63  */
  64 static void
  65 scc_tarjan_strongconnect(unsigned int *scc_counter,
  66                          struct REGEX_INTERNAL_State *v, unsigned int *index,
  67                          struct REGEX_INTERNAL_State **stack,
  68                          unsigned int *stack_size)
  69 {
  70   struct REGEX_INTERNAL_State *w;
  71   struct REGEX_INTERNAL_Transition *t;
  72
  73   v->index = *index;
  74   v->lowlink = *index;
  75   (*index)++;
  76   stack[(*stack_size)++] = v;
  77   v->contained = 1;
  78
  79   for (t = v->transitions_head; NULL != t; t = t->next)
  80     {
  81       w = t->to_state;
  82
  83       if (NULL == w)
  84         continue;
  85
  86       if (w->index < 0)
  87         {
  88           scc_tarjan_strongconnect(scc_counter, w, index, stack, stack_size);
  89           v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink;
  90         }
  91       else if (1 == w->contained)
  92         v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink;
  93     }
  94
  95   if (v->lowlink == v->index)
  96     {
  97       (*scc_counter)++;
  98       do
  99         {
 100           w = stack[--(*stack_size)];
 101           w->contained = 0;
 102           w->scc_id = *scc_counter;
 103         }
 104       while (w != v);
 105     }
 106 }
 107
 108
 109 /**
 110  * Detect all SCCs (Strongly Connected Components) inside the given automaton.
 111  * SCCs will be marked using the scc_id on each state.
 112  *
 113  * @param a the automaton for which SCCs should be computed and assigned.
 114  */
 115 static void
 116 scc_tarjan(struct REGEX_INTERNAL_Automaton *a)
 117 {
 118   unsigned int index;
 119   unsigned int scc_counter;
 120   struct REGEX_INTERNAL_State *v;
 121   struct REGEX_INTERNAL_State *stack[a->state_count];
 122   unsigned int stack_size;
 123
 124   for (v = a->states_head; NULL != v; v = v->next)
 125     {
 126       v->contained = 0;
 127       v->index = -1;
 128       v->lowlink = -1;
 129     }
 130
 131   stack_size = 0;
 132   index = 0;
 133   scc_counter = 0;
 134
 135   for (v = a->states_head; NULL != v; v = v->next)
 136     {
 137       if (v->index < 0)
 138         scc_tarjan_strongconnect(&scc_counter, v, &index, stack, &stack_size);
 139     }
 140 }
 141
 142
 143 /**
 144  * Save a state to an open file pointer. cls is expected to be a file pointer to
 145  * an open file. Used only in conjunction with
 146  * REGEX_TEST_automaton_save_graph.
 147  *
 148  * @param cls file pointer.
 149  * @param count current count of the state, not used.
 150  * @param s state.
 151  */
 152 void
 153 REGEX_TEST_automaton_save_graph_step(void *cls, unsigned int count,
 154                                      struct REGEX_INTERNAL_State *s)
 155 {
 156   struct REGEX_TEST_Graph_Context *ctx = cls;
 157   struct REGEX_INTERNAL_Transition *ctran;
 158   char *s_acc = NULL;
 159   char *s_tran = NULL;
 160   char *name;
 161   char *to_name;
 162
 163   if (GNUNET_YES == ctx->verbose)
 164     GNUNET_asprintf(&name, "%i (%s) (%s) (%s)", s->dfs_id, s->name, s->proof,
 165                     GNUNET_h2s(&s->hash));
 166   else
 167     GNUNET_asprintf(&name, "%i", s->dfs_id);
 168
 169   if (s->accepting)
 170     {
 171       if (GNUNET_YES == ctx->coloring)
 172         {
 173           GNUNET_asprintf(&s_acc,
 174                           "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
 175                           name, s->scc_id * s->scc_id);
 176         }
 177       else
 178         {
 179           GNUNET_asprintf(&s_acc, "\"%s\" [shape=doublecircle];\n", name,
 180                           s->scc_id);
 181         }
 182     }
 183   else if (GNUNET_YES == ctx->coloring)
 184     {
 185       GNUNET_asprintf(&s_acc,
 186                       "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name,
 187                       s->scc_id * s->scc_id);
 188     }
 189   else
 190     {
 191       GNUNET_asprintf(&s_acc, "\"%s\" [shape=circle];\n", name, s->scc_id);
 192     }
 193
 194   GNUNET_assert(NULL != s_acc);
 195
 196   fwrite(s_acc, strlen(s_acc), 1, ctx->filep);
 197   GNUNET_free(s_acc);
 198   s_acc = NULL;
 199
 200   for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
 201     {
 202       if (NULL == ctran->to_state)
 203         {
 204           GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
 205                      "Transition from State %i has no state for transitioning\n",
 206                      s->id);
 207           continue;
 208         }
 209
 210       if (GNUNET_YES == ctx->verbose)
 211         {
 212           GNUNET_asprintf(&to_name, "%i (%s) (%s) (%s)", ctran->to_state->dfs_id,
 213                           ctran->to_state->name, ctran->to_state->proof,
 214                           GNUNET_h2s(&ctran->to_state->hash));
 215         }
 216       else
 217         GNUNET_asprintf(&to_name, "%i", ctran->to_state->dfs_id);
 218
 219       if (NULL == ctran->label)
 220         {
 221           if (GNUNET_YES == ctx->coloring)
 222             {
 223               GNUNET_asprintf(&s_tran,
 224                               "\"%s\" -> \"%s\" [label = \"ε\", color=\"0.%i 0.8 0.95\"];\n",
 225                               name, to_name, s->scc_id * s->scc_id);
 226             }
 227           else
 228             {
 229               GNUNET_asprintf(&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name,
 230                               to_name, s->scc_id);
 231             }
 232         }
 233       else
 234         {
 235           if (GNUNET_YES == ctx->coloring)
 236             {
 237               GNUNET_asprintf(&s_tran,
 238                               "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 0.95\"];\n",
 239                               name, to_name, ctran->label, s->scc_id * s->scc_id);
 240             }
 241           else
 242             {
 243               GNUNET_asprintf(&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name,
 244                               to_name, ctran->label, s->scc_id);
 245             }
 246         }
 247
 248       GNUNET_free(to_name);
 249
 250       GNUNET_assert(NULL != s_tran);
 251
 252       fwrite(s_tran, strlen(s_tran), 1, ctx->filep);
 253       GNUNET_free(s_tran);
 254       s_tran = NULL;
 255     }
 256
 257   GNUNET_free(name);
 258 }
 259
 260
 261 /**
 262  * Save the given automaton as a GraphViz dot file.
 263  *
 264  * @param a the automaton to be saved.
 265  * @param filename where to save the file.
 266  * @param options options for graph generation that include coloring or verbose
 267  *                mode
 268  */
 269 void
 270 REGEX_TEST_automaton_save_graph(struct REGEX_INTERNAL_Automaton *a,
 271                                 const char *filename,
 272                                 enum REGEX_TEST_GraphSavingOptions options)
 273 {
 274   char *start;
 275   char *end;
 276   struct REGEX_TEST_Graph_Context ctx;
 277
 278   if (NULL == a)
 279     {
 280       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
 281       return;
 282     }
 283
 284   if (NULL == filename || strlen(filename) < 1)
 285     {
 286       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
 287       return;
 288     }
 289
 290   ctx.filep = fopen(filename, "w");
 291   ctx.verbose =
 292     (0 == (options & REGEX_TEST_GRAPH_VERBOSE)) ? GNUNET_NO : GNUNET_YES;
 293   ctx.coloring =
 294     (0 == (options & REGEX_TEST_GRAPH_COLORING)) ? GNUNET_NO : GNUNET_YES;
 295
 296   if (NULL == ctx.filep)
 297     {
 298       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
 299                  filename);
 300       return;
 301     }
 302
 303   /* First add the SCCs to the automaton, so we can color them nicely */
 304   if (GNUNET_YES == ctx.coloring)
 305     scc_tarjan(a);
 306
 307   start = "digraph G {\nrankdir=LR\n";
 308   fwrite(start, strlen(start), 1, ctx.filep);
 309
 310   REGEX_INTERNAL_automaton_traverse(a, a->start, NULL, NULL,
 311                                     &REGEX_TEST_automaton_save_graph_step,
 312                                     &ctx);
 313
 314   end = "\n}\n";
 315   fwrite(end, strlen(end), 1, ctx.filep);
 316   fclose(ctx.filep);
 317 }