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  * Recursive function doing DFS with 'v' as a start, detecting all SCCs inside
  31  * the subgraph reachable from 'v'. Used with scc_tarjan function to detect all
  32  * SCCs inside an automaton.
  33  *
  34  * @param scc_counter counter for numbering the sccs
  35  * @param v start vertex
  36  * @param index current index
  37  * @param stack stack for saving all SCCs
  38  * @param stack_size current size of the stack
  39  */
  40 static void
  41 scc_tarjan_strongconnect (unsigned int *scc_counter,
  42                           struct GNUNET_REGEX_State *v, unsigned int *index,
  43                           struct GNUNET_REGEX_State **stack,
  44                           unsigned int *stack_size)
  45 {
  46   struct GNUNET_REGEX_State *w;
  47   struct GNUNET_REGEX_Transition *t;
  48
  49   v->index = *index;
  50   v->lowlink = *index;
  51   (*index)++;
  52   stack[(*stack_size)++] = v;
  53   v->contained = 1;
  54
  55   for (t = v->transitions_head; NULL != t; t = t->next)
  56   {
  57     w = t->to_state;
  58     if (NULL != w && w->index < 0)
  59     {
  60       scc_tarjan_strongconnect (scc_counter, w, index, stack, stack_size);
  61       v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink;
  62     }
  63     else if (0 != w->contained)
  64       v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink;
  65   }
  66
  67   if (v->lowlink == v->index)
  68   {
  69     w = stack[--(*stack_size)];
  70     w->contained = 0;
  71
  72     if (v != w)
  73     {
  74       (*scc_counter)++;
  75       while (v != w)
  76       {
  77         w->scc_id = *scc_counter;
  78         w = stack[--(*stack_size)];
  79         w->contained = 0;
  80       }
  81       w->scc_id = *scc_counter;
  82     }
  83   }
  84 }
  85
  86
  87 /**
  88  * Detect all SCCs (Strongly Connected Components) inside the given automaton.
  89  * SCCs will be marked using the scc_id on each state.
  90  *
  91  * @param a the automaton for which SCCs should be computed and assigned.
  92  */
  93 static void
  94 scc_tarjan (struct GNUNET_REGEX_Automaton *a)
  95 {
  96   unsigned int index;
  97   unsigned int scc_counter;
  98   struct GNUNET_REGEX_State *v;
  99   struct GNUNET_REGEX_State *stack[a->state_count];
 100   unsigned int stack_size;
 101
 102   for (v = a->states_head; NULL != v; v = v->next)
 103   {
 104     v->contained = 0;
 105     v->index = -1;
 106     v->lowlink = -1;
 107   }
 108
 109   stack_size = 0;
 110   index = 0;
 111   scc_counter = 0;
 112
 113   for (v = a->states_head; NULL != v; v = v->next)
 114   {
 115     if (v->index < 0)
 116       scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size);
 117   }
 118 }
 119
 120
 121 /**
 122  * Save a state to an open file pointer. cls is expected to be a file pointer to
 123  * an open file. Used only in conjunction with
 124  * GNUNET_REGEX_automaton_save_graph.
 125  *
 126  * @param cls file pointer.
 127  * @param count current count of the state, not used.
 128  * @param s state.
 129  */
 130 void
 131 GNUNET_REGEX_automaton_save_graph_step (void *cls, unsigned int count,
 132                                         struct GNUNET_REGEX_State *s)
 133 {
 134   FILE *p;
 135   struct GNUNET_REGEX_Transition *ctran;
 136   char *s_acc = NULL;
 137   char *s_tran = NULL;
 138
 139   p = cls;
 140
 141   if (s->accepting)
 142   {
 143     GNUNET_asprintf (&s_acc,
 144                      "\"%s(%i)\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
 145                      s->name, s->proof_id, s->scc_id);
 146   }
 147   else
 148   {
 149     GNUNET_asprintf (&s_acc, "\"%s(%i)\" [color=\"0.%i 0.8 0.95\"];\n", s->name,
 150                      s->proof_id, s->scc_id);
 151   }
 152
 153   if (NULL == s_acc)
 154   {
 155     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print state %s\n", s->name);
 156     return;
 157   }
 158   fwrite (s_acc, strlen (s_acc), 1, p);
 159   GNUNET_free (s_acc);
 160   s_acc = NULL;
 161
 162   for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
 163   {
 164     if (NULL == ctran->to_state)
 165     {
 166       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 167                   "Transition from State %i has no state for transitioning\n",
 168                   s->id);
 169       continue;
 170     }
 171
 172     if (ctran->label == 0)
 173     {
 174       GNUNET_asprintf (&s_tran,
 175                        "\"%s(%i)\" -> \"%s(%i)\" [label = \"epsilon\", color=\"0.%i 0.8 0.95\"];\n",
 176                        s->name, s->proof_id, ctran->to_state->name,
 177                        ctran->to_state->proof_id, s->scc_id);
 178     }
 179     else
 180     {
 181       GNUNET_asprintf (&s_tran,
 182                        "\"%s(%i)\" -> \"%s(%i)\" [label = \"%c\", color=\"0.%i 0.8 0.95\"];\n",
 183                        s->name, s->proof_id, ctran->to_state->name,
 184                        ctran->to_state->proof_id, ctran->label, s->scc_id);
 185     }
 186
 187     if (NULL == s_tran)
 188     {
 189       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print state %s\n",
 190                   s->name);
 191       return;
 192     }
 193
 194     fwrite (s_tran, strlen (s_tran), 1, p);
 195     GNUNET_free (s_tran);
 196     s_tran = NULL;
 197   }
 198 }
 199
 200
 201 /**
 202  * Save the given automaton as a GraphViz dot file
 203  *
 204  * @param a the automaton to be saved
 205  * @param filename where to save the file
 206  */
 207 void
 208 GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a,
 209                                    const char *filename)
 210 {
 211   char *start;
 212   char *end;
 213   FILE *p;
 214
 215   if (NULL == a)
 216   {
 217     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
 218     return;
 219   }
 220
 221   if (NULL == filename || strlen (filename) < 1)
 222   {
 223     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
 224     return;
 225   }
 226
 227   p = fopen (filename, "w");
 228
 229   if (NULL == p)
 230   {
 231     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
 232                 filename);
 233     return;
 234   }
 235
 236   /* First add the SCCs to the automaton, so we can color them nicely */
 237   scc_tarjan (a);
 238
 239   start = "digraph G {\nrankdir=LR\n";
 240   fwrite (start, strlen (start), 1, p);
 241
 242   GNUNET_REGEX_automaton_traverse (a, &GNUNET_REGEX_automaton_save_graph_step,
 243                                    p);
 244
 245   end = "\n}\n";
 246   fwrite (end, strlen (end), 1, p);
 247   fclose (p);
 248 }