regex_test_graph.c File Reference

#include "platform.h"
#include "regex_internal_lib.h"
#include "regex_test_lib.h"
#include "regex_internal.h"

Include dependency graph for regex_test_graph.c:

Go to the source code of this file.

Data Structures
struct	REGEX_TEST_Graph_Context
	Context for graph creation. More...

Functions
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)
	Recursive function doing DFS with 'v' as a start, detecting all SCCs inside the subgraph reachable from 'v'. More...
static void	scc_tarjan (struct REGEX_INTERNAL_Automaton *a)
	Detect all SCCs (Strongly Connected Components) inside the given automaton. More...
void	REGEX_TEST_automaton_save_graph_step (void *cls, unsigned int count, struct REGEX_INTERNAL_State *s)
	Save a state to an open file pointer. More...
void	REGEX_TEST_automaton_save_graph (struct REGEX_INTERNAL_Automaton *a, const char *filename, enum REGEX_TEST_GraphSavingOptions options)
	Save the given automaton as a GraphViz dot file. More...

Function Documentation

scc_tarjan_strongconnect()

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  )

static

Recursive function doing DFS with 'v' as a start, detecting all SCCs inside the subgraph reachable from 'v'.

Used with scc_tarjan function to detect all SCCs inside an automaton.

Parameters

scc_counter	counter for numbering the sccs
v	start vertex
index	current index
stack	stack for saving all SCCs
stack_size	current size of the stack

Definition at line 66 of file regex_test_graph.c.

{
  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);
  }
}

References REGEX_INTERNAL_State::contained, REGEX_INTERNAL_State::index, REGEX_INTERNAL_State::lowlink, GNUNET_SCHEDULER_Task::next, REGEX_INTERNAL_State::scc_id, scc_tarjan_strongconnect(), t, and REGEX_INTERNAL_State::transitions_head.

Referenced by scc_tarjan(), and scc_tarjan_strongconnect().

Here is the call graph for this function:

Here is the caller graph for this function:

scc_tarjan()

static void scc_tarjan ( struct REGEX_INTERNAL_Automaton *  a )

static

Detect all SCCs (Strongly Connected Components) inside the given automaton.

SCCs will be marked using the scc_id on each state.

Parameters

a	the automaton for which SCCs should be computed and assigned.

Definition at line 117 of file regex_test_graph.c.

{
  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);
  }
}

References REGEX_INTERNAL_State::contained, REGEX_INTERNAL_State::index, REGEX_INTERNAL_State::lowlink, REGEX_INTERNAL_State::next, scc_tarjan_strongconnect(), REGEX_INTERNAL_Automaton::state_count, and REGEX_INTERNAL_Automaton::states_head.

Referenced by REGEX_TEST_automaton_save_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_TEST_automaton_save_graph_step()

void REGEX_TEST_automaton_save_graph_step	(	void *	cls,
		unsigned int	count,
		struct REGEX_INTERNAL_State *	s
	)

Save a state to an open file pointer.

cls is expected to be a file pointer to an open file. Used only in conjunction with REGEX_TEST_automaton_save_graph.

Parameters

cls	file pointer.
count	current count of the state, not used.
s	state.

Definition at line 154 of file regex_test_graph.c.

{
  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);
    }
  }
  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);
  }
 
  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);
      }
    }
    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);
      }
    }
 
    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);
}

References REGEX_INTERNAL_State::accepting, ctx, REGEX_INTERNAL_State::dfs_id, GNUNET_asprintf(), GNUNET_assert, GNUNET_ERROR_TYPE_ERROR, GNUNET_free, GNUNET_h2s(), GNUNET_log, GNUNET_YES, REGEX_INTERNAL_State::hash, REGEX_INTERNAL_State::id, REGEX_INTERNAL_Transition::label, name, REGEX_INTERNAL_State::name, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::proof, REGEX_INTERNAL_State::scc_id, REGEX_INTERNAL_Transition::to_state, and REGEX_INTERNAL_State::transitions_head.

Referenced by REGEX_TEST_automaton_save_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

REGEX_TEST_automaton_save_graph()

void REGEX_TEST_automaton_save_graph	(	struct REGEX_INTERNAL_Automaton *	a,
		const char *	filename,
		enum REGEX_TEST_GraphSavingOptions	options
	)

Save the given automaton as a GraphViz dot file.

Parameters

a	the automaton to be saved.
filename	where to save the file.
options	options for graph generation that include coloring or verbose mode

Definition at line 270 of file regex_test_graph.c.

{
  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);
}

References ctx, end, filename, GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_NO, GNUNET_YES, options, REGEX_INTERNAL_automaton_traverse(), REGEX_TEST_automaton_save_graph_step(), REGEX_TEST_GRAPH_COLORING, REGEX_TEST_GRAPH_VERBOSE, scc_tarjan(), start, and REGEX_INTERNAL_Automaton::start.

Here is the call graph for this function: