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