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