GNUnet 0.21.0
regex_test_graph.c
Go to the documentation of this file.
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 */
25#include "platform.h"
26#include "regex_internal_lib.h"
27#include "regex_test_lib.h"
28#include "regex_internal.h"
29
35{
39 FILE *filep;
40
46
51};
52
53
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;
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
116static void
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
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 {
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
258}
259
260
269void
271 const char *filename,
273{
274 char *start;
275 char *end;
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 =
293 ctx.coloring =
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,
312 &ctx);
313
314 end = "\n}\n";
315 fwrite (end, strlen (end), 1, ctx.filep);
316 fclose (ctx.filep);
317}
struct GNUNET_GETOPT_CommandLineOption options[]
Definition: 002.c:5
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
static struct GNUNET_FS_Handle * ctx
static char * filename
static char * name
Name (label) of the records to list.
static struct GNUNET_SCHEDULER_Task * t
Main task.
#define GNUNET_log(kind,...)
@ GNUNET_YES
@ GNUNET_NO
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
@ GNUNET_ERROR_TYPE_ERROR
int int GNUNET_asprintf(char **buf, const char *format,...) __attribute__((format(printf
Like asprintf, just portable.
#define GNUNET_free(ptr)
Wrapper around free.
void REGEX_INTERNAL_automaton_traverse(const struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *start, REGEX_INTERNAL_traverse_check check, void *check_cls, REGEX_INTERNAL_traverse_action action, void *action_cls)
Traverses the given automaton using depth-first-search (DFS) from it's start state,...
library to parse regular expressions into dfa
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.
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 fr...
static void scc_tarjan(struct REGEX_INTERNAL_Automaton *a)
Detect all SCCs (Strongly Connected Components) inside the given automaton.
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.
REGEX_TEST_GraphSavingOptions
Options for graph creation function REGEX_TEST_automaton_save_graph.
@ REGEX_TEST_GRAPH_COLORING
Enable graph coloring.
@ REGEX_TEST_GRAPH_VERBOSE
The generated graph will include extra information such as the NFA states that were used to generate ...
struct GNUNET_SCHEDULER_Task * next
This is a linked list.
Definition: scheduler.c:140
Automaton representation.
struct REGEX_INTERNAL_State * start
First state of the automaton.
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
char * proof
Proof for this state.
unsigned int dfs_id
Linear state ID acquired by depth-first-search.
char * name
Human readable name of the state.
unsigned int id
Unique state id.
int accepting
If this is an accepting state or not.
int lowlink
Used for SCC detection.
int contained
Marking the state as contained.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
struct GNUNET_HashCode hash
Hash of the state.
int index
Used for SCC detection.
unsigned int scc_id
Marking the state as part of an SCC (Strongly Connected Component).
Transition between two states.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
char * label
Label for this transition.
Context for graph creation.
int verbose
Verbose flag, if it's set to GNUNET_YES additional info will be printed in the graph.
int coloring
Coloring flag, if set to GNUNET_YES SCCs will be colored.
FILE * filep
File pointer to the dot file used for output.