src/regex/regex_graph.c

   1 /*
   2      This file is part of GNUnet
   3      (C) 2012 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      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      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20 /**
  21  * @file src/regex/regex_graph.c
  22  * @brief functions for creating .dot graphs from regexes
  23  * @author Maximilian Szengel
  24  */
  25 #include "platform.h"
  26 #include "gnunet_regex_lib.h"
  27 #include "regex_internal.h"
  28
  29 /**
  30  * Context for graph creation. Passed as the cls to
  31  * GNUNET_REGEX_automaton_save_graph_step.
  32  */
  33 struct GNUNET_REGEX_Graph_Context
  34 {
  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
  48 /**
  49  * Recursive function doing DFS with 'v' as a start, detecting all SCCs inside
  50  * the subgraph reachable from 'v'. Used with scc_tarjan function to detect all
  51  * SCCs inside an automaton.
  52  *
  53  * @param scc_counter counter for numbering the sccs
  54  * @param v start vertex
  55  * @param index current index
  56  * @param stack stack for saving all SCCs
  57  * @param stack_size current size of the stack
  58  */
  59 static void
  60 scc_tarjan_strongconnect (unsigned int *scc_counter,
  61                           struct GNUNET_REGEX_State *v, unsigned int *index,
  62                           struct GNUNET_REGEX_State **stack,
  63                           unsigned int *stack_size)
  64 {
  65   struct GNUNET_REGEX_State *w;
  66   struct GNUNET_REGEX_Transition *t;
  67
  68   v->index = *index;
  69   v->lowlink = *index;
  70   (*index)++;
  71   stack[(*stack_size)++] = v;
  72   v->contained = 1;
  73
  74   for (t = v->transitions_head; NULL != t; t = t->next)
  75   {
  76     w = t->to_state;
  77
  78     if (NULL == w)
  79       continue;
  80
  81     if (w->index < 0)
  82     {
  83       scc_tarjan_strongconnect (scc_counter, w, index, stack, stack_size);
  84       v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink;
  85     }
  86     else if (0 != w->contained)
  87       v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink;
  88   }
  89
  90   if (v->lowlink == v->index)
  91   {
  92     w = stack[--(*stack_size)];
  93     w->contained = 0;
  94
  95     if (v != w)
  96     {
  97       (*scc_counter)++;
  98       while (v != w)
  99       {
 100         w->scc_id = *scc_counter;
 101         w = stack[--(*stack_size)];
 102         w->contained = 0;
 103       }
 104       w->scc_id = *scc_counter;
 105     }
 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 GNUNET_REGEX_Automaton *a)
 118 {
 119   unsigned int index;
 120   unsigned int scc_counter;
 121   struct GNUNET_REGEX_State *v;
 122   struct GNUNET_REGEX_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  * GNUNET_REGEX_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 GNUNET_REGEX_automaton_save_graph_step (void *cls, unsigned int count,
 155                                         struct GNUNET_REGEX_State *s)
 156 {
 157   struct GNUNET_REGEX_Graph_Context *ctx = cls;
 158   struct GNUNET_REGEX_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->proof_id, s->name, s->proof,
 166                      GNUNET_h2s (&s->hash));
 167   else
 168     GNUNET_asprintf (&name, "%i", s->proof_id);
 169
 170   if (s->accepting)
 171   {
 172     GNUNET_asprintf (&s_acc,
 173                      "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
 174                      name, s->scc_id);
 175   }
 176   else
 177   {
 178     GNUNET_asprintf (&s_acc, "\"%s\" [color=\"0.%i 0.8 0.95\"];\n", name,
 179                      s->scc_id);
 180   }
 181
 182   if (NULL == s_acc)
 183   {
 184     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print state %s\n", s->name);
 185     return;
 186   }
 187   fwrite (s_acc, strlen (s_acc), 1, ctx->filep);
 188   GNUNET_free (s_acc);
 189   s_acc = NULL;
 190
 191   for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
 192   {
 193     if (NULL == ctran->to_state)
 194     {
 195       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 196                   "Transition from State %i has no state for transitioning\n",
 197                   s->id);
 198       continue;
 199     }
 200
 201     if (GNUNET_YES == ctx->verbose)
 202     {
 203       GNUNET_asprintf (&to_name, "%i (%s) (%s) (%s)", ctran->to_state->proof_id,
 204                        ctran->to_state->name, ctran->to_state->proof,
 205                        GNUNET_h2s (&ctran->to_state->hash));
 206     }
 207     else
 208       GNUNET_asprintf (&to_name, "%i", ctran->to_state->proof_id);
 209
 210     if (ctran->label == 0)
 211     {
 212       GNUNET_asprintf (&s_tran,
 213                        "\"%s\" -> \"%s\" [label = \"epsilon\", color=\"0.%i 0.8 0.95\"];\n",
 214                        name, to_name, s->scc_id);
 215     }
 216     else
 217     {
 218       GNUNET_asprintf (&s_tran,
 219                        "\"%s\" -> \"%s\" [label = \"%c\", color=\"0.%i 0.8 0.95\"];\n",
 220                        name, to_name, ctran->label, s->scc_id);
 221     }
 222
 223     GNUNET_free (to_name);
 224
 225     if (NULL == s_tran)
 226     {
 227       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print state %s\n",
 228                   s->name);
 229       return;
 230     }
 231
 232     fwrite (s_tran, strlen (s_tran), 1, ctx->filep);
 233     GNUNET_free (s_tran);
 234     s_tran = NULL;
 235   }
 236
 237   GNUNET_free (name);
 238 }
 239
 240
 241 /**
 242  * Save the given automaton as a GraphViz dot file
 243  *
 244  * @param a the automaton to be saved
 245  * @param filename where to save the file
 246  * @param verbose if set to GNUNET_YES the generated graph will include extra
 247  *                information such as the NFA states that were used to generate
 248  *                the DFA state etc.
 249  */
 250 void
 251 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
 252                                    const char *filename, int verbose)
 253 {
 254   char *start;
 255   char *end;
 256   struct GNUNET_REGEX_Graph_Context ctx;
 257
 258   if (NULL == a)
 259   {
 260     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
 261     return;
 262   }
 263
 264   if (NULL == filename || strlen (filename) < 1)
 265   {
 266     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
 267     return;
 268   }
 269
 270   ctx.filep = fopen (filename, "w");
 271   ctx.verbose = verbose;
 272
 273   if (NULL == ctx.filep)
 274   {
 275     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
 276                 filename);
 277     return;
 278   }
 279
 280   /* First add the SCCs to the automaton, so we can color them nicely */
 281   scc_tarjan (a);
 282
 283   start = "digraph G {\nrankdir=LR\n";
 284   fwrite (start, strlen (start), 1, ctx.filep);
 285
 286   GNUNET_REGEX_automaton_traverse (a, &GNUNET_REGEX_automaton_save_graph_step,
 287                                    &ctx);
 288
 289   end = "\n}\n";
 290   fwrite (end, strlen (end), 1, ctx.filep);
 291   fclose (ctx.filep);
 292 }