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   /**
  37    * File pointer to the dot file used for output.
  38    */
  39   FILE *filep;
  40
  41   /**
  42    * Verbose flag, if it's set to GNUNET_YES additional info will be printed in
  43    * the graph.
  44    */
  45   int verbose;
  46
  47   /**
  48    * Coloring flag, if set to GNUNET_YES SCCs will be colored.
  49    */
  50   int coloring;
  51 };
  52
  53
  54 /**
  55  * Recursive function doing DFS with 'v' as a start, detecting all SCCs inside
  56  * the subgraph reachable from 'v'. Used with scc_tarjan function to detect all
  57  * SCCs inside an automaton.
  58  *
  59  * @param scc_counter counter for numbering the sccs
  60  * @param v start vertex
  61  * @param index current index
  62  * @param stack stack for saving all SCCs
  63  * @param stack_size current size of the stack
  64  */
  65 static void
  66 scc_tarjan_strongconnect (unsigned int *scc_counter,
  67                           struct REGEX_INTERNAL_State *v, unsigned int *index,
  68                           struct REGEX_INTERNAL_State **stack,
  69                           unsigned int *stack_size)
  70 {
  71   struct REGEX_INTERNAL_State *w;
  72   struct REGEX_INTERNAL_Transition *t;
  73
  74   v->index = *index;
  75   v->lowlink = *index;
  76   (*index)++;
  77   stack[(*stack_size)++] = v;
  78   v->contained = 1;
  79
  80   for (t = v->transitions_head; NULL != t; t = t->next)
  81   {
  82     w = t->to_state;
  83
  84     if (NULL == w)
  85       continue;
  86
  87     if (w->index < 0)
  88     {
  89       scc_tarjan_strongconnect (scc_counter, w, index, stack, stack_size);
  90       v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink;
  91     }
  92     else if (1 == w->contained)
  93       v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink;
  94   }
  95
  96   if (v->lowlink == v->index)
  97   {
  98     (*scc_counter)++;
  99     do
 100     {
 101       w = stack[--(*stack_size)];
 102       w->contained = 0;
 103       w->scc_id = *scc_counter;
 104     }
 105     while (w != v);
 106   }
 107 }
 108
 109
 110 /**
 111  * Detect all SCCs (Strongly Connected Components) inside the given automaton.
 112  * SCCs will be marked using the scc_id on each state.
 113  *
 114  * @param a the automaton for which SCCs should be computed and assigned.
 115  */
 116 static void
 117 scc_tarjan (struct REGEX_INTERNAL_Automaton *a)
 118 {
 119   unsigned int index;
 120   unsigned int scc_counter;
 121   struct REGEX_INTERNAL_State *v;
 122   struct REGEX_INTERNAL_State *stack[a->state_count];
 123   unsigned int stack_size;
 124
 125   for (v = a->states_head; NULL != v; v = v->next)
 126   {
 127     v->contained = 0;
 128     v->index = -1;
 129     v->lowlink = -1;
 130   }
 131
 132   stack_size = 0;
 133   index = 0;
 134   scc_counter = 0;
 135
 136   for (v = a->states_head; NULL != v; v = v->next)
 137   {
 138     if (v->index < 0)
 139       scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size);
 140   }
 141 }
 142
 143
 144 /**
 145  * Save a state to an open file pointer. cls is expected to be a file pointer to
 146  * an open file. Used only in conjunction with
 147  * REGEX_TEST_automaton_save_graph.
 148  *
 149  * @param cls file pointer.
 150  * @param count current count of the state, not used.
 151  * @param s state.
 152  */
 153 void
 154 REGEX_TEST_automaton_save_graph_step (void *cls, unsigned int count,
 155                                         struct REGEX_INTERNAL_State *s)
 156 {
 157   struct REGEX_TEST_Graph_Context *ctx = cls;
 158   struct REGEX_INTERNAL_Transition *ctran;
 159   char *s_acc = NULL;
 160   char *s_tran = NULL;
 161   char *name;
 162   char *to_name;
 163
 164   if (GNUNET_YES == ctx->verbose)
 165     GNUNET_asprintf (&name, "%i (%s) (%s) (%s)", s->dfs_id, s->name, s->proof,
 166                      GNUNET_h2s (&s->hash));
 167   else
 168     GNUNET_asprintf (&name, "%i", s->dfs_id);
 169
 170   if (s->accepting)
 171   {
 172     if (GNUNET_YES == ctx->coloring)
 173     {
 174       GNUNET_asprintf (&s_acc,
 175                        "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
 176                        name, s->scc_id * s->scc_id);
 177     }
 178     else
 179     {
 180       GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", name,
 181                        s->scc_id);
 182     }
 183   }
 184   else if (GNUNET_YES == ctx->coloring)
 185   {
 186     GNUNET_asprintf (&s_acc,
 187                      "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name,
 188                      s->scc_id * s->scc_id);
 189   }
 190   else
 191   {
 192     GNUNET_asprintf (&s_acc, "\"%s\" [shape=circle];\n", name, s->scc_id);
 193   }
 194
 195   GNUNET_assert (NULL != s_acc);
 196
 197   fwrite (s_acc, strlen (s_acc), 1, ctx->filep);
 198   GNUNET_free (s_acc);
 199   s_acc = NULL;
 200
 201   for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
 202   {
 203     if (NULL == ctran->to_state)
 204     {
 205       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 206                   "Transition from State %i has no state for transitioning\n",
 207                   s->id);
 208       continue;
 209     }
 210
 211     if (GNUNET_YES == ctx->verbose)
 212     {
 213       GNUNET_asprintf (&to_name, "%i (%s) (%s) (%s)", ctran->to_state->dfs_id,
 214                        ctran->to_state->name, ctran->to_state->proof,
 215                        GNUNET_h2s (&ctran->to_state->hash));
 216     }
 217     else
 218       GNUNET_asprintf (&to_name, "%i", ctran->to_state->dfs_id);
 219
 220     if (NULL == ctran->label)
 221     {
 222       if (GNUNET_YES == ctx->coloring)
 223       {
 224         GNUNET_asprintf (&s_tran,
 225                          "\"%s\" -> \"%s\" [label = \"ε\", color=\"0.%i 0.8 0.95\"];\n",
 226                          name, to_name, s->scc_id * s->scc_id);
 227       }
 228       else
 229       {
 230         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name,
 231                          to_name, s->scc_id);
 232       }
 233     }
 234     else
 235     {
 236       if (GNUNET_YES == ctx->coloring)
 237       {
 238         GNUNET_asprintf (&s_tran,
 239                          "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 0.95\"];\n",
 240                          name, to_name, ctran->label, s->scc_id * s->scc_id);
 241       }
 242       else
 243       {
 244         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name,
 245                          to_name, ctran->label, s->scc_id);
 246       }
 247     }
 248
 249     GNUNET_free (to_name);
 250
 251     GNUNET_assert (NULL != s_tran);
 252
 253     fwrite (s_tran, strlen (s_tran), 1, ctx->filep);
 254     GNUNET_free (s_tran);
 255     s_tran = NULL;
 256   }
 257
 258   GNUNET_free (name);
 259 }
 260
 261
 262 /**
 263  * Save the given automaton as a GraphViz dot file.
 264  *
 265  * @param a the automaton to be saved.
 266  * @param filename where to save the file.
 267  * @param options options for graph generation that include coloring or verbose
 268  *                mode
 269  */
 270 void
 271 REGEX_TEST_automaton_save_graph (struct REGEX_INTERNAL_Automaton *a,
 272                                    const char *filename,
 273                                    enum REGEX_TEST_GraphSavingOptions options)
 274 {
 275   char *start;
 276   char *end;
 277   struct REGEX_TEST_Graph_Context ctx;
 278
 279   if (NULL == a)
 280   {
 281     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
 282     return;
 283   }
 284
 285   if (NULL == filename || strlen (filename) < 1)
 286   {
 287     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
 288     return;
 289   }
 290
 291   ctx.filep = fopen (filename, "w");
 292   ctx.verbose =
 293       (0 == (options & REGEX_TEST_GRAPH_VERBOSE)) ? GNUNET_NO : GNUNET_YES;
 294   ctx.coloring =
 295       (0 == (options & REGEX_TEST_GRAPH_COLORING)) ? GNUNET_NO : GNUNET_YES;
 296
 297   if (NULL == ctx.filep)
 298   {
 299     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
 300                 filename);
 301     return;
 302   }
 303
 304   /* First add the SCCs to the automaton, so we can color them nicely */
 305   if (GNUNET_YES == ctx.coloring)
 306     scc_tarjan (a);
 307
 308   start = "digraph G {\nrankdir=LR\n";
 309   fwrite (start, strlen (start), 1, ctx.filep);
 310
 311   REGEX_INTERNAL_automaton_traverse (a, a->start, NULL, NULL,
 312                                    &REGEX_TEST_automaton_save_graph_step,
 313                                    &ctx);
 314
 315   end = "\n}\n";
 316   fwrite (end, strlen (end), 1, ctx.filep);
 317   fclose (ctx.filep);
 318 }