diff options
Diffstat (limited to 'src/regex/regex_test_graph.c')
-rw-r--r-- | src/regex/regex_test_graph.c | 316 |
1 files changed, 316 insertions, 0 deletions
diff --git a/src/regex/regex_test_graph.c b/src/regex/regex_test_graph.c new file mode 100644 index 000000000..d8f16e894 --- /dev/null +++ b/src/regex/regex_test_graph.c | |||
@@ -0,0 +1,316 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet | ||
3 | Copyright (C) 2012 GNUnet e.V. | ||
4 | |||
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. | ||
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 | Affero General Public License for more details. | ||
14 | |||
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/>. | ||
17 | */ | ||
18 | /** | ||
19 | * @file src/regex/regex_test_graph.c | ||
20 | * @brief functions for creating .dot graphs from regexes | ||
21 | * @author Maximilian Szengel | ||
22 | */ | ||
23 | #include "platform.h" | ||
24 | #include "regex_internal_lib.h" | ||
25 | #include "regex_test_lib.h" | ||
26 | #include "regex_internal.h" | ||
27 | |||
28 | /** | ||
29 | * Context for graph creation. Passed as the cls to | ||
30 | * REGEX_TEST_automaton_save_graph_step. | ||
31 | */ | ||
32 | struct REGEX_TEST_Graph_Context | ||
33 | { | ||
34 | /** | ||
35 | * File pointer to the dot file used for output. | ||
36 | */ | ||
37 | FILE *filep; | ||
38 | |||
39 | /** | ||
40 | * Verbose flag, if it's set to GNUNET_YES additional info will be printed in | ||
41 | * the graph. | ||
42 | */ | ||
43 | int verbose; | ||
44 | |||
45 | /** | ||
46 | * Coloring flag, if set to GNUNET_YES SCCs will be colored. | ||
47 | */ | ||
48 | int coloring; | ||
49 | }; | ||
50 | |||
51 | |||
52 | /** | ||
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. | ||
56 | * | ||
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 | ||
62 | */ | ||
63 | static void | ||
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) | ||
68 | { | ||
69 | struct REGEX_INTERNAL_State *w; | ||
70 | struct REGEX_INTERNAL_Transition *t; | ||
71 | |||
72 | v->index = *index; | ||
73 | v->lowlink = *index; | ||
74 | (*index)++; | ||
75 | stack[(*stack_size)++] = v; | ||
76 | v->contained = 1; | ||
77 | |||
78 | for (t = v->transitions_head; NULL != t; t = t->next) | ||
79 | { | ||
80 | w = t->to_state; | ||
81 | |||
82 | if (NULL == w) | ||
83 | continue; | ||
84 | |||
85 | if (w->index < 0) | ||
86 | { | ||
87 | scc_tarjan_strongconnect (scc_counter, w, index, stack, stack_size); | ||
88 | v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink; | ||
89 | } | ||
90 | else if (1 == w->contained) | ||
91 | v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink; | ||
92 | } | ||
93 | |||
94 | if (v->lowlink == v->index) | ||
95 | { | ||
96 | (*scc_counter)++; | ||
97 | do | ||
98 | { | ||
99 | w = stack[--(*stack_size)]; | ||
100 | w->contained = 0; | ||
101 | w->scc_id = *scc_counter; | ||
102 | } | ||
103 | while (w != v); | ||
104 | } | ||
105 | } | ||
106 | |||
107 | |||
108 | /** | ||
109 | * Detect all SCCs (Strongly Connected Components) inside the given automaton. | ||
110 | * SCCs will be marked using the scc_id on each state. | ||
111 | * | ||
112 | * @param a the automaton for which SCCs should be computed and assigned. | ||
113 | */ | ||
114 | static void | ||
115 | scc_tarjan (struct REGEX_INTERNAL_Automaton *a) | ||
116 | { | ||
117 | unsigned int index; | ||
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; | ||
122 | |||
123 | for (v = a->states_head; NULL != v; v = v->next) | ||
124 | { | ||
125 | v->contained = 0; | ||
126 | v->index = -1; | ||
127 | v->lowlink = -1; | ||
128 | } | ||
129 | |||
130 | stack_size = 0; | ||
131 | index = 0; | ||
132 | scc_counter = 0; | ||
133 | |||
134 | for (v = a->states_head; NULL != v; v = v->next) | ||
135 | { | ||
136 | if (v->index < 0) | ||
137 | scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size); | ||
138 | } | ||
139 | } | ||
140 | |||
141 | |||
142 | /** | ||
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. | ||
146 | * | ||
147 | * @param cls file pointer. | ||
148 | * @param count current count of the state, not used. | ||
149 | * @param s state. | ||
150 | */ | ||
151 | void | ||
152 | REGEX_TEST_automaton_save_graph_step (void *cls, unsigned int count, | ||
153 | struct REGEX_INTERNAL_State *s) | ||
154 | { | ||
155 | struct REGEX_TEST_Graph_Context *ctx = cls; | ||
156 | struct REGEX_INTERNAL_Transition *ctran; | ||
157 | char *s_acc = NULL; | ||
158 | char *s_tran = NULL; | ||
159 | char *name; | ||
160 | char *to_name; | ||
161 | |||
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)); | ||
165 | else | ||
166 | GNUNET_asprintf (&name, "%i", s->dfs_id); | ||
167 | |||
168 | if (s->accepting) | ||
169 | { | ||
170 | if (GNUNET_YES == ctx->coloring) | ||
171 | { | ||
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); | ||
175 | } | ||
176 | else | ||
177 | { | ||
178 | GNUNET_asprintf (&s_acc, "\"%s\" [shape=doublecircle];\n", name, | ||
179 | s->scc_id); | ||
180 | } | ||
181 | } | ||
182 | else if (GNUNET_YES == ctx->coloring) | ||
183 | { | ||
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); | ||
187 | } | ||
188 | else | ||
189 | { | ||
190 | GNUNET_asprintf (&s_acc, "\"%s\" [shape=circle];\n", name, s->scc_id); | ||
191 | } | ||
192 | |||
193 | GNUNET_assert (NULL != s_acc); | ||
194 | |||
195 | fwrite (s_acc, strlen (s_acc), 1, ctx->filep); | ||
196 | GNUNET_free (s_acc); | ||
197 | s_acc = NULL; | ||
198 | |||
199 | for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next) | ||
200 | { | ||
201 | if (NULL == ctran->to_state) | ||
202 | { | ||
203 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
204 | "Transition from State %i has no state for transitioning\n", | ||
205 | s->id); | ||
206 | continue; | ||
207 | } | ||
208 | |||
209 | if (GNUNET_YES == ctx->verbose) | ||
210 | { | ||
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)); | ||
214 | } | ||
215 | else | ||
216 | GNUNET_asprintf (&to_name, "%i", ctran->to_state->dfs_id); | ||
217 | |||
218 | if (NULL == ctran->label) | ||
219 | { | ||
220 | if (GNUNET_YES == ctx->coloring) | ||
221 | { | ||
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); | ||
225 | } | ||
226 | else | ||
227 | { | ||
228 | GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name, | ||
229 | to_name, s->scc_id); | ||
230 | } | ||
231 | } | ||
232 | else | ||
233 | { | ||
234 | if (GNUNET_YES == ctx->coloring) | ||
235 | { | ||
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); | ||
239 | } | ||
240 | else | ||
241 | { | ||
242 | GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name, | ||
243 | to_name, ctran->label, s->scc_id); | ||
244 | } | ||
245 | } | ||
246 | |||
247 | GNUNET_free (to_name); | ||
248 | |||
249 | GNUNET_assert (NULL != s_tran); | ||
250 | |||
251 | fwrite (s_tran, strlen (s_tran), 1, ctx->filep); | ||
252 | GNUNET_free (s_tran); | ||
253 | s_tran = NULL; | ||
254 | } | ||
255 | |||
256 | GNUNET_free (name); | ||
257 | } | ||
258 | |||
259 | |||
260 | /** | ||
261 | * Save the given automaton as a GraphViz dot file. | ||
262 | * | ||
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 | ||
266 | * mode | ||
267 | */ | ||
268 | void | ||
269 | REGEX_TEST_automaton_save_graph (struct REGEX_INTERNAL_Automaton *a, | ||
270 | const char *filename, | ||
271 | enum REGEX_TEST_GraphSavingOptions options) | ||
272 | { | ||
273 | char *start; | ||
274 | char *end; | ||
275 | struct REGEX_TEST_Graph_Context ctx; | ||
276 | |||
277 | if (NULL == a) | ||
278 | { | ||
279 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!"); | ||
280 | return; | ||
281 | } | ||
282 | |||
283 | if (NULL == filename || strlen (filename) < 1) | ||
284 | { | ||
285 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!"); | ||
286 | return; | ||
287 | } | ||
288 | |||
289 | ctx.filep = fopen (filename, "w"); | ||
290 | ctx.verbose = | ||
291 | (0 == (options & REGEX_TEST_GRAPH_VERBOSE)) ? GNUNET_NO : GNUNET_YES; | ||
292 | ctx.coloring = | ||
293 | (0 == (options & REGEX_TEST_GRAPH_COLORING)) ? GNUNET_NO : GNUNET_YES; | ||
294 | |||
295 | if (NULL == ctx.filep) | ||
296 | { | ||
297 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s", | ||
298 | filename); | ||
299 | return; | ||
300 | } | ||
301 | |||
302 | /* First add the SCCs to the automaton, so we can color them nicely */ | ||
303 | if (GNUNET_YES == ctx.coloring) | ||
304 | scc_tarjan (a); | ||
305 | |||
306 | start = "digraph G {\nrankdir=LR\n"; | ||
307 | fwrite (start, strlen (start), 1, ctx.filep); | ||
308 | |||
309 | REGEX_INTERNAL_automaton_traverse (a, a->start, NULL, NULL, | ||
310 | ®EX_TEST_automaton_save_graph_step, | ||
311 | &ctx); | ||
312 | |||
313 | end = "\n}\n"; | ||
314 | fwrite (end, strlen (end), 1, ctx.filep); | ||
315 | fclose (ctx.filep); | ||
316 | } | ||