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    * 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 GNUNET_REGEX_State *v, unsigned int *index,
  67                           struct GNUNET_REGEX_State **stack,
  68                           unsigned int *stack_size)
  69 {
  70   struct GNUNET_REGEX_State *w;
  71   struct GNUNET_REGEX_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 (0 != w->contained)
  92       v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink;
  93   }
  94
  95   if (v->lowlink == v->index)
  96   {
  97     w = stack[--(*stack_size)];
  98     w->contained = 0;
  99
 100     if (v != w)
 101     {
 102       (*scc_counter)++;
 103       while (v != w)
 104       {
 105         w->scc_id = *scc_counter;
 106         w = stack[--(*stack_size)];
 107         w->contained = 0;
 108       }
 109       w->scc_id = *scc_counter;
 110     }
 111   }
 112 }
 113
 114
 115 /**
 116  * Detect all SCCs (Strongly Connected Components) inside the given automaton.
 117  * SCCs will be marked using the scc_id on each state.
 118  *
 119  * @param a the automaton for which SCCs should be computed and assigned.
 120  */
 121 static void
 122 scc_tarjan (struct GNUNET_REGEX_Automaton *a)
 123 {
 124   unsigned int index;
 125   unsigned int scc_counter;
 126   struct GNUNET_REGEX_State *v;
 127   struct GNUNET_REGEX_State *stack[a->state_count];
 128   unsigned int stack_size;
 129
 130   for (v = a->states_head; NULL != v; v = v->next)
 131   {
 132     v->contained = 0;
 133     v->index = -1;
 134     v->lowlink = -1;
 135   }
 136
 137   stack_size = 0;
 138   index = 0;
 139   scc_counter = 0;
 140
 141   for (v = a->states_head; NULL != v; v = v->next)
 142   {
 143     if (v->index < 0)
 144       scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size);
 145   }
 146 }
 147
 148
 149 /**
 150  * Save a state to an open file pointer. cls is expected to be a file pointer to
 151  * an open file. Used only in conjunction with
 152  * GNUNET_REGEX_automaton_save_graph.
 153  *
 154  * @param cls file pointer.
 155  * @param count current count of the state, not used.
 156  * @param s state.
 157  */
 158 void
 159 GNUNET_REGEX_automaton_save_graph_step (void *cls, unsigned int count,
 160                                         struct GNUNET_REGEX_State *s)
 161 {
 162   struct GNUNET_REGEX_Graph_Context *ctx = cls;
 163   struct GNUNET_REGEX_Transition *ctran;
 164   char *s_acc = NULL;
 165   char *s_tran = NULL;
 166   char *name;
 167   char *to_name;
 168
 169   if (GNUNET_YES == ctx->verbose)
 170     GNUNET_asprintf (&name, "%i (%s) (%s) (%s)", s->proof_id, s->name, s->proof,
 171                      GNUNET_h2s (&s->hash));
 172   else
 173     GNUNET_asprintf (&name, "%i", s->proof_id);
 174
 175   if (s->accepting)
 176   {
 177     if (GNUNET_YES == ctx->coloring)
 178     {
 179       GNUNET_asprintf (&s_acc,
 180                        "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
 181                        name, s->scc_id);
 182     }
 183     else
 184     {
 185       GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", name,
 186                        s->scc_id);
 187     }
 188   }
 189   else if (GNUNET_YES == ctx->coloring)
 190   {
 191     GNUNET_asprintf (&s_acc,
 192                      "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name,
 193                      s->scc_id);
 194   }
 195   else
 196   {
 197     GNUNET_asprintf (&s_acc, "\"%s\" [shape=circle];\n", name, s->scc_id);
 198   }
 199
 200   if (NULL == s_acc)
 201   {
 202     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print state %s\n", s->name);
 203     return;
 204   }
 205   fwrite (s_acc, strlen (s_acc), 1, ctx->filep);
 206   GNUNET_free (s_acc);
 207   s_acc = NULL;
 208
 209   for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
 210   {
 211     if (NULL == ctran->to_state)
 212     {
 213       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 214                   "Transition from State %i has no state for transitioning\n",
 215                   s->id);
 216       continue;
 217     }
 218
 219     if (GNUNET_YES == ctx->verbose)
 220     {
 221       GNUNET_asprintf (&to_name, "%i (%s) (%s) (%s)", ctran->to_state->proof_id,
 222                        ctran->to_state->name, ctran->to_state->proof,
 223                        GNUNET_h2s (&ctran->to_state->hash));
 224     }
 225     else
 226       GNUNET_asprintf (&to_name, "%i", ctran->to_state->proof_id);
 227
 228     if (NULL == ctran->label)
 229     {
 230       if (GNUNET_YES == ctx->coloring)
 231       {
 232         GNUNET_asprintf (&s_tran,
 233                          "\"%s\" -> \"%s\" [label = \"ε\", color=\"0.%i 0.8 0.95\"];\n",
 234                          name, to_name, s->scc_id);
 235       }
 236       else
 237       {
 238         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name,
 239                          to_name, s->scc_id);
 240       }
 241     }
 242     else
 243     {
 244       if (GNUNET_YES == ctx->coloring)
 245       {
 246         GNUNET_asprintf (&s_tran,
 247                          "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 0.95\"];\n",
 248                          name, to_name, ctran->label, s->scc_id);
 249       }
 250       else
 251       {
 252         GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name,
 253                          to_name, ctran->label, s->scc_id);
 254       }
 255     }
 256
 257     GNUNET_free (to_name);
 258
 259     if (NULL == s_tran)
 260     {
 261       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print state %s\n",
 262                   s->name);
 263       return;
 264     }
 265
 266     fwrite (s_tran, strlen (s_tran), 1, ctx->filep);
 267     GNUNET_free (s_tran);
 268     s_tran = NULL;
 269   }
 270
 271   GNUNET_free (name);
 272 }
 273
 274
 275 /**
 276  * Save the given automaton as a GraphViz dot file.
 277  *
 278  * @param a the automaton to be saved.
 279  * @param filename where to save the file.
 280  * @param options options for graph generation that include coloring or verbose
 281  *                mode
 282  */
 283 void
 284 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
 285                                    const char *filename,
 286                                    enum GNUNET_REGEX_GraphSavingOptions options)
 287 {
 288   char *start;
 289   char *end;
 290   struct GNUNET_REGEX_Graph_Context ctx;
 291
 292   if (NULL == a)
 293   {
 294     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
 295     return;
 296   }
 297
 298   if (NULL == filename || strlen (filename) < 1)
 299   {
 300     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
 301     return;
 302   }
 303
 304   ctx.filep = fopen (filename, "w");
 305   ctx.verbose =
 306       (0 == (options & GNUNET_REGEX_GRAPH_VERBOSE)) ? GNUNET_NO : GNUNET_YES;
 307   ctx.coloring =
 308       (0 == (options & GNUNET_REGEX_GRAPH_COLORING)) ? GNUNET_NO : GNUNET_YES;
 309
 310   if (NULL == ctx.filep)
 311   {
 312     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
 313                 filename);
 314     return;
 315   }
 316
 317   /* First add the SCCs to the automaton, so we can color them nicely */
 318   scc_tarjan (a);
 319
 320   start = "digraph G {\nrankdir=LR\n";
 321   fwrite (start, strlen (start), 1, ctx.filep);
 322
 323   GNUNET_REGEX_automaton_traverse (a, &GNUNET_REGEX_automaton_save_graph_step,
 324                                    &ctx);
 325
 326   end = "\n}\n";
 327   fwrite (end, strlen (end), 1, ctx.filep);
 328   fclose (ctx.filep);
 329 }