2 This file is part of GNUnet
3 Copyright (C) 2012 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
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 Affero General Public License for more details.
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
19 * @file src/regex/regex_test_graph.c
20 * @brief functions for creating .dot graphs from regexes
21 * @author Maximilian Szengel
24 #include "regex_internal_lib.h"
25 #include "regex_test_lib.h"
26 #include "regex_internal.h"
29 * Context for graph creation. Passed as the cls to
30 * REGEX_TEST_automaton_save_graph_step.
32 struct REGEX_TEST_Graph_Context
35 * File pointer to the dot file used for output.
40 * Verbose flag, if it's set to GNUNET_YES additional info will be printed in
46 * Coloring flag, if set to GNUNET_YES SCCs will be colored.
53 * Recursive function doing DFS with 'v' as a start, detecting all SCCs inside
54 * the subgraph reachable from 'v'. Used with scc_tarjan function to detect all
55 * SCCs inside an automaton.
57 * @param scc_counter counter for numbering the sccs
58 * @param v start vertex
59 * @param index current index
60 * @param stack stack for saving all SCCs
61 * @param stack_size current size of the stack
64 scc_tarjan_strongconnect (unsigned int *scc_counter,
65 struct REGEX_INTERNAL_State *v, unsigned int *index,
66 struct REGEX_INTERNAL_State **stack,
67 unsigned int *stack_size)
69 struct REGEX_INTERNAL_State *w;
70 struct REGEX_INTERNAL_Transition *t;
75 stack[(*stack_size)++] = v;
78 for (t = v->transitions_head; NULL != t; t = t->next)
87 scc_tarjan_strongconnect (scc_counter, w, index, stack, stack_size);
88 v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink;
90 else if (1 == w->contained)
91 v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink;
94 if (v->lowlink == v->index)
99 w = stack[--(*stack_size)];
101 w->scc_id = *scc_counter;
109 * Detect all SCCs (Strongly Connected Components) inside the given automaton.
110 * SCCs will be marked using the scc_id on each state.
112 * @param a the automaton for which SCCs should be computed and assigned.
115 scc_tarjan (struct REGEX_INTERNAL_Automaton *a)
118 unsigned int scc_counter;
119 struct REGEX_INTERNAL_State *v;
120 struct REGEX_INTERNAL_State *stack[a->state_count];
121 unsigned int stack_size;
123 for (v = a->states_head; NULL != v; v = v->next)
134 for (v = a->states_head; NULL != v; v = v->next)
137 scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size);
143 * Save a state to an open file pointer. cls is expected to be a file pointer to
144 * an open file. Used only in conjunction with
145 * REGEX_TEST_automaton_save_graph.
147 * @param cls file pointer.
148 * @param count current count of the state, not used.
152 REGEX_TEST_automaton_save_graph_step (void *cls, unsigned int count,
153 struct REGEX_INTERNAL_State *s)
155 struct REGEX_TEST_Graph_Context *ctx = cls;
156 struct REGEX_INTERNAL_Transition *ctran;
162 if (GNUNET_YES == ctx->verbose)
163 GNUNET_asprintf (&name, "%i (%s) (%s) (%s)", s->dfs_id, s->name, s->proof,
164 GNUNET_h2s (&s->hash));
166 GNUNET_asprintf (&name, "%i", s->dfs_id);
170 if (GNUNET_YES == ctx->coloring)
172 GNUNET_asprintf (&s_acc,
173 "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
174 name, s->scc_id * s->scc_id);
178 GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", name,
182 else if (GNUNET_YES == ctx->coloring)
184 GNUNET_asprintf (&s_acc,
185 "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name,
186 s->scc_id * s->scc_id);
190 GNUNET_asprintf (&s_acc, "\"%s\" [shape=circle];\n", name, s->scc_id);
193 GNUNET_assert (NULL != s_acc);
195 fwrite (s_acc, strlen (s_acc), 1, ctx->filep);
199 for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next)
201 if (NULL == ctran->to_state)
203 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
204 "Transition from State %i has no state for transitioning\n",
209 if (GNUNET_YES == ctx->verbose)
211 GNUNET_asprintf (&to_name, "%i (%s) (%s) (%s)", ctran->to_state->dfs_id,
212 ctran->to_state->name, ctran->to_state->proof,
213 GNUNET_h2s (&ctran->to_state->hash));
216 GNUNET_asprintf (&to_name, "%i", ctran->to_state->dfs_id);
218 if (NULL == ctran->label)
220 if (GNUNET_YES == ctx->coloring)
222 GNUNET_asprintf (&s_tran,
223 "\"%s\" -> \"%s\" [label = \"ε\", color=\"0.%i 0.8 0.95\"];\n",
224 name, to_name, s->scc_id * s->scc_id);
228 GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name,
234 if (GNUNET_YES == ctx->coloring)
236 GNUNET_asprintf (&s_tran,
237 "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 0.95\"];\n",
238 name, to_name, ctran->label, s->scc_id * s->scc_id);
242 GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name,
243 to_name, ctran->label, s->scc_id);
247 GNUNET_free (to_name);
249 GNUNET_assert (NULL != s_tran);
251 fwrite (s_tran, strlen (s_tran), 1, ctx->filep);
252 GNUNET_free (s_tran);
261 * Save the given automaton as a GraphViz dot file.
263 * @param a the automaton to be saved.
264 * @param filename where to save the file.
265 * @param options options for graph generation that include coloring or verbose
269 REGEX_TEST_automaton_save_graph (struct REGEX_INTERNAL_Automaton *a,
270 const char *filename,
271 enum REGEX_TEST_GraphSavingOptions options)
275 struct REGEX_TEST_Graph_Context ctx;
279 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!");
283 if (NULL == filename || strlen (filename) < 1)
285 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!");
289 ctx.filep = fopen (filename, "w");
291 (0 == (options & REGEX_TEST_GRAPH_VERBOSE)) ? GNUNET_NO : GNUNET_YES;
293 (0 == (options & REGEX_TEST_GRAPH_COLORING)) ? GNUNET_NO : GNUNET_YES;
295 if (NULL == ctx.filep)
297 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s",
302 /* First add the SCCs to the automaton, so we can color them nicely */
303 if (GNUNET_YES == ctx.coloring)
306 start = "digraph G {\nrankdir=LR\n";
307 fwrite (start, strlen (start), 1, ctx.filep);
309 REGEX_INTERNAL_automaton_traverse (a, a->start, NULL, NULL,
310 ®EX_TEST_automaton_save_graph_step,
314 fwrite (end, strlen (end), 1, ctx.filep);