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