regex_test_graph.c

Go to the documentation of this file.

/*
     This file is part of GNUnet
     Copyright (C) 2012 GNUnet e.V.

     GNUnet is free software: you can redistribute it and/or modify it
     under the terms of the GNU Affero General Public License as published
     by the Free Software Foundation, either version 3 of the License,
     or (at your option) any later version.

     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     Affero General Public License for more details.

     You should have received a copy of the GNU Affero General Public License
     along with this program.  If not, see <http://www.gnu.org/licenses/>.

     SPDX-License-Identifier: AGPL3.0-or-later
 */
#include "platform.h"
#include "regex_internal_lib.h"
#include "regex_test_lib.h"
#include "regex_internal.h"

struct REGEX_TEST_Graph_Context {
  FILE *filep;

  int verbose;

  int coloring;
};


static void
scc_tarjan_strongconnect(unsigned int *scc_counter,
                         struct REGEX_INTERNAL_State *v, unsigned int *index,
                         struct REGEX_INTERNAL_State **stack,
                         unsigned int *stack_size)
{
  struct REGEX_INTERNAL_State *w;
  struct REGEX_INTERNAL_Transition *t;

  v->index = *index;
  v->lowlink = *index;
  (*index)++;
  stack[(*stack_size)++] = v;
  v->contained = 1;

  for (t = v->transitions_head; NULL != t; t = t->next)
    {
      w = t->to_state;

      if (NULL == w)
        continue;

      if (w->index < 0)
        {
          scc_tarjan_strongconnect(scc_counter, w, index, stack, stack_size);
          v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink;
        }
      else if (1 == w->contained)
        v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink;
    }

  if (v->lowlink == v->index)
    {
      (*scc_counter)++;
      do
        {
          w = stack[--(*stack_size)];
          w->contained = 0;
          w->scc_id = *scc_counter;
        }
      while (w != v);
    }
}


static void
scc_tarjan(struct REGEX_INTERNAL_Automaton *a)
{
  unsigned int index;
  unsigned int scc_counter;
  struct REGEX_INTERNAL_State *v;
  struct REGEX_INTERNAL_State *stack[a->state_count];
  unsigned int stack_size;

  for (v = a->states_head; NULL != v; v = v->next)
    {
      v->contained = 0;
      v->index = -1;
      v->lowlink = -1;
    }

  stack_size = 0;
  index = 0;
  scc_counter = 0;

  for (v = a->states_head; NULL != v; v = v->next)
    {
      if (v->index < 0)
        scc_tarjan_strongconnect(&scc_counter, v, &index, stack, &stack_size);
    }
}


void
REGEX_TEST_automaton_save_graph_step(void *cls, unsigned int count,
                                     struct REGEX_INTERNAL_State *s)
{
  struct REGEX_TEST_Graph_Context *ctx = cls;
  struct REGEX_INTERNAL_Transition *ctran;
  char *s_acc = NULL;
  char *s_tran = NULL;
  char *name;
  char *to_name;

  if (GNUNET_YES == ctx->verbose)
    GNUNET_asprintf(&name, "%i (%s) (%s) (%s)", s->dfs_id, s->name, s->proof,
                    GNUNET_h2s(&s->hash));
  else
    GNUNET_asprintf(&name, "%i", s->dfs_id);

  if (s->accepting)
    {
      if (GNUNET_YES == ctx->coloring)
        {
          GNUNET_asprintf(&s_acc,
                          "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
                          name, s->scc_id * s->scc_id);
        }
      else
        {
          GNUNET_asprintf(&s_acc, "\"%s\" [shape=doublecircle];\n", name,
                          s->scc_id);
        }
    }
  else if (GNUNET_YES == ctx->coloring)
    {
      GNUNET_asprintf(&s_acc,
                      "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name,
                      s->scc_id * s->scc_id);
    }
  else
    {
      GNUNET_asprintf(&s_acc, "\"%s\" [shape=circle];\n", name, s->scc_id);
    }

  GNUNET_assert(NULL != s_acc);

  fwrite(s_acc, strlen(s_acc), 1, ctx->filep);
  GNUNET_free(s_acc);
  s_acc = NULL;

  for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
    {
      if (NULL == ctran->to_state)
        {
          GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
                     "Transition from State %i has no state for transitioning\n",
                     s->id);
          continue;
        }

      if (GNUNET_YES == ctx->verbose)
        {
          GNUNET_asprintf(&to_name, "%i (%s) (%s) (%s)", ctran->to_state->dfs_id,
                          ctran->to_state->name, ctran->to_state->proof,
                          GNUNET_h2s(&ctran->to_state->hash));
        }
      else
        GNUNET_asprintf(&to_name, "%i", ctran->to_state->dfs_id);

      if (NULL == ctran->label)
        {
          if (GNUNET_YES == ctx->coloring)
            {
              GNUNET_asprintf(&s_tran,
                              "\"%s\" -> \"%s\" [label = \"ε\", color=\"0.%i 0.8 0.95\"];\n",
                              name, to_name, s->scc_id * s->scc_id);
            }
          else
            {
              GNUNET_asprintf(&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name,
                              to_name, s->scc_id);
            }
        }
      else
        {
          if (GNUNET_YES == ctx->coloring)
            {
              GNUNET_asprintf(&s_tran,
                              "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 0.95\"];\n",
                              name, to_name, ctran->label, s->scc_id * s->scc_id);
            }
          else
            {
              GNUNET_asprintf(&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name,
                              to_name, ctran->label, s->scc_id);
            }
        }

      GNUNET_free(to_name);

      GNUNET_assert(NULL != s_tran);

      fwrite(s_tran, strlen(s_tran), 1, ctx->filep);
      GNUNET_free(s_tran);
      s_tran = NULL;
    }

  GNUNET_free(name);
}


void
REGEX_TEST_automaton_save_graph(struct REGEX_INTERNAL_Automaton *a,
                                const char *filename,
                                enum REGEX_TEST_GraphSavingOptions options)
{
  char *start;
  char *end;
  struct REGEX_TEST_Graph_Context ctx;

  if (NULL == a)
    {
      GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
      return;
    }

  if (NULL == filename || strlen(filename) < 1)
    {
      GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
      return;
    }

  ctx.filep = fopen(filename, "w");
  ctx.verbose =
    (0 == (options & REGEX_TEST_GRAPH_VERBOSE)) ? GNUNET_NO : GNUNET_YES;
  ctx.coloring =
    (0 == (options & REGEX_TEST_GRAPH_COLORING)) ? GNUNET_NO : GNUNET_YES;

  if (NULL == ctx.filep)
    {
      GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
                 filename);
      return;
    }

  /* First add the SCCs to the automaton, so we can color them nicely */
  if (GNUNET_YES == ctx.coloring)
    scc_tarjan(a);

  start = "digraph G {\nrankdir=LR\n";
  fwrite(start, strlen(start), 1, ctx.filep);

  REGEX_INTERNAL_automaton_traverse(a, a->start, NULL, NULL,
                                    &REGEX_TEST_automaton_save_graph_step,
                                    &ctx);

  end = "\n}\n";
  fwrite(end, strlen(end), 1, ctx.filep);
  fclose(ctx.filep);
}