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