* Context for graph creation. Passed as the cls to
* REGEX_TEST_automaton_save_graph_step.
*/
-struct REGEX_TEST_Graph_Context {
+struct REGEX_TEST_Graph_Context
+{
/**
* File pointer to the dot file used for output.
*/
* @param stack_size current size of the stack
*/
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)
+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->contained = 1;
for (t = v->transitions_head; NULL != t; t = t->next)
+ {
+ w = t->to_state;
+
+ if (NULL == w)
+ continue;
+
+ if (w->index < 0)
{
- 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;
+ 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
{
- (*scc_counter)++;
- do
- {
- w = stack[--(*stack_size)];
- w->contained = 0;
- w->scc_id = *scc_counter;
- }
- while (w != v);
+ w = stack[--(*stack_size)];
+ w->contained = 0;
+ w->scc_id = *scc_counter;
}
+ while (w != v);
+ }
}
* @param a the automaton for which SCCs should be computed and assigned.
*/
static void
-scc_tarjan(struct REGEX_INTERNAL_Automaton *a)
+scc_tarjan (struct REGEX_INTERNAL_Automaton *a)
{
unsigned int index;
unsigned int scc_counter;
unsigned int stack_size;
for (v = a->states_head; NULL != v; v = v->next)
- {
- v->contained = 0;
- v->index = -1;
- v->lowlink = -1;
- }
+ {
+ 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);
- }
+ {
+ if (v->index < 0)
+ scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size);
+ }
}
* @param s state.
*/
void
-REGEX_TEST_automaton_save_graph_step(void *cls, unsigned int count,
- struct REGEX_INTERNAL_State *s)
+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 *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));
+ 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);
+ GNUNET_asprintf (&name, "%i", s->dfs_id);
if (s->accepting)
+ {
+ if (GNUNET_YES == ctx->coloring)
{
- 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);
- }
+ GNUNET_asprintf (&s_acc,
+ "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
+ name, s->scc_id * s->scc_id);
}
- else if (GNUNET_YES == ctx->coloring)
+ else
{
- GNUNET_asprintf(&s_acc,
- "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name,
- s->scc_id * s->scc_id);
+ 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_asprintf (&s_acc, "\"%s\" [shape=circle];\n", name, s->scc_id);
+ }
- GNUNET_assert(NULL != s_acc);
+ GNUNET_assert (NULL != s_acc);
- fwrite(s_acc, strlen(s_acc), 1, ctx->filep);
- GNUNET_free(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 (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));
- }
+ 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(&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);
- }
- }
+ {
+ 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
- {
- 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_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name,
+ to_name, ctran->label, s->scc_id);
+ }
}
- GNUNET_free(name);
+ 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);
}
* mode
*/
void
-REGEX_TEST_automaton_save_graph(struct REGEX_INTERNAL_Automaton *a,
- const char *filename,
- enum REGEX_TEST_GraphSavingOptions options)
+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");
+ {
+ 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;
- }
+ {
+ 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);
+ scc_tarjan (a);
start = "digraph G {\nrankdir=LR\n";
- fwrite(start, strlen(start), 1, ctx.filep);
+ fwrite (start, strlen (start), 1, ctx.filep);
- REGEX_INTERNAL_automaton_traverse(a, a->start, NULL, NULL,
- ®EX_TEST_automaton_save_graph_step,
- &ctx);
+ REGEX_INTERNAL_automaton_traverse (a, a->start, NULL, NULL,
+ ®EX_TEST_automaton_save_graph_step,
+ &ctx);
end = "\n}\n";
- fwrite(end, strlen(end), 1, ctx.filep);
- fclose(ctx.filep);
+ fwrite (end, strlen (end), 1, ctx.filep);
+ fclose (ctx.filep);
}
projects / oweals / gnunet.git / blobdiff