diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-07-04 13:54:43 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-07-04 13:54:43 +0000 |
commit | bd0e2cd49ae9ae916f6a4288ac8893128b8168d6 (patch) | |
tree | c680e35f3d2bb3cffb114808bd19f2299885af50 /src/regex/regex_graph.c | |
parent | a93954693fef730d7a41c168b4961d19e5dff90c (diff) | |
download | gnunet-bd0e2cd49ae9ae916f6a4288ac8893128b8168d6.tar.gz gnunet-bd0e2cd49ae9ae916f6a4288ac8893128b8168d6.zip |
Summary: regex cleanup and bugfixes
Author: szengel
Diffstat (limited to 'src/regex/regex_graph.c')
-rw-r--r-- | src/regex/regex_graph.c | 248 |
1 files changed, 248 insertions, 0 deletions
diff --git a/src/regex/regex_graph.c b/src/regex/regex_graph.c new file mode 100644 index 000000000..3230ea702 --- /dev/null +++ b/src/regex/regex_graph.c | |||
@@ -0,0 +1,248 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet | ||
3 | (C) 2012 Christian Grothoff (and other contributing authors) | ||
4 | |||
5 | GNUnet is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 3, or (at your | ||
8 | 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 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
18 | Boston, MA 02111-1307, USA. | ||
19 | */ | ||
20 | /** | ||
21 | * @file src/regex/regex_graph.c | ||
22 | * @brief functions for creating .dot graphs from regexes | ||
23 | * @author Maximilian Szengel | ||
24 | */ | ||
25 | #include "platform.h" | ||
26 | #include "gnunet_regex_lib.h" | ||
27 | #include "regex_internal.h" | ||
28 | |||
29 | /** | ||
30 | * Recursive function doing DFS with 'v' as a start, detecting all SCCs inside | ||
31 | * the subgraph reachable from 'v'. Used with scc_tarjan function to detect all | ||
32 | * SCCs inside an automaton. | ||
33 | * | ||
34 | * @param scc_counter counter for numbering the sccs | ||
35 | * @param v start vertex | ||
36 | * @param index current index | ||
37 | * @param stack stack for saving all SCCs | ||
38 | * @param stack_size current size of the stack | ||
39 | */ | ||
40 | static void | ||
41 | scc_tarjan_strongconnect (unsigned int *scc_counter, | ||
42 | struct GNUNET_REGEX_State *v, unsigned int *index, | ||
43 | struct GNUNET_REGEX_State **stack, | ||
44 | unsigned int *stack_size) | ||
45 | { | ||
46 | struct GNUNET_REGEX_State *w; | ||
47 | struct GNUNET_REGEX_Transition *t; | ||
48 | |||
49 | v->index = *index; | ||
50 | v->lowlink = *index; | ||
51 | (*index)++; | ||
52 | stack[(*stack_size)++] = v; | ||
53 | v->contained = 1; | ||
54 | |||
55 | for (t = v->transitions_head; NULL != t; t = t->next) | ||
56 | { | ||
57 | w = t->to_state; | ||
58 | if (NULL != w && w->index < 0) | ||
59 | { | ||
60 | scc_tarjan_strongconnect (scc_counter, w, index, stack, stack_size); | ||
61 | v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink; | ||
62 | } | ||
63 | else if (0 != w->contained) | ||
64 | v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink; | ||
65 | } | ||
66 | |||
67 | if (v->lowlink == v->index) | ||
68 | { | ||
69 | w = stack[--(*stack_size)]; | ||
70 | w->contained = 0; | ||
71 | |||
72 | if (v != w) | ||
73 | { | ||
74 | (*scc_counter)++; | ||
75 | while (v != w) | ||
76 | { | ||
77 | w->scc_id = *scc_counter; | ||
78 | w = stack[--(*stack_size)]; | ||
79 | w->contained = 0; | ||
80 | } | ||
81 | w->scc_id = *scc_counter; | ||
82 | } | ||
83 | } | ||
84 | } | ||
85 | |||
86 | |||
87 | /** | ||
88 | * Detect all SCCs (Strongly Connected Components) inside the given automaton. | ||
89 | * SCCs will be marked using the scc_id on each state. | ||
90 | * | ||
91 | * @param a the automaton for which SCCs should be computed and assigned. | ||
92 | */ | ||
93 | static void | ||
94 | scc_tarjan (struct GNUNET_REGEX_Automaton *a) | ||
95 | { | ||
96 | unsigned int index; | ||
97 | unsigned int scc_counter; | ||
98 | struct GNUNET_REGEX_State *v; | ||
99 | struct GNUNET_REGEX_State *stack[a->state_count]; | ||
100 | unsigned int stack_size; | ||
101 | |||
102 | for (v = a->states_head; NULL != v; v = v->next) | ||
103 | { | ||
104 | v->contained = 0; | ||
105 | v->index = -1; | ||
106 | v->lowlink = -1; | ||
107 | } | ||
108 | |||
109 | stack_size = 0; | ||
110 | index = 0; | ||
111 | scc_counter = 0; | ||
112 | |||
113 | for (v = a->states_head; NULL != v; v = v->next) | ||
114 | { | ||
115 | if (v->index < 0) | ||
116 | scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size); | ||
117 | } | ||
118 | } | ||
119 | |||
120 | |||
121 | /** | ||
122 | * Save a state to an open file pointer. cls is expected to be a file pointer to | ||
123 | * an open file. Used only in conjunction with | ||
124 | * GNUNET_REGEX_automaton_save_graph. | ||
125 | * | ||
126 | * @param cls file pointer. | ||
127 | * @param count current count of the state, not used. | ||
128 | * @param s state. | ||
129 | */ | ||
130 | void | ||
131 | GNUNET_REGEX_automaton_save_graph_step (void *cls, unsigned int count, | ||
132 | struct GNUNET_REGEX_State *s) | ||
133 | { | ||
134 | FILE *p; | ||
135 | struct GNUNET_REGEX_Transition *ctran; | ||
136 | char *s_acc = NULL; | ||
137 | char *s_tran = NULL; | ||
138 | |||
139 | p = cls; | ||
140 | |||
141 | if (s->accepting) | ||
142 | { | ||
143 | GNUNET_asprintf (&s_acc, | ||
144 | "\"%s(%i)\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n", | ||
145 | s->name, s->proof_id, s->scc_id); | ||
146 | } | ||
147 | else | ||
148 | { | ||
149 | GNUNET_asprintf (&s_acc, "\"%s(%i)\" [color=\"0.%i 0.8 0.95\"];\n", s->name, | ||
150 | s->proof_id, s->scc_id); | ||
151 | } | ||
152 | |||
153 | if (NULL == s_acc) | ||
154 | { | ||
155 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print state %s\n", s->name); | ||
156 | return; | ||
157 | } | ||
158 | fwrite (s_acc, strlen (s_acc), 1, p); | ||
159 | GNUNET_free (s_acc); | ||
160 | s_acc = NULL; | ||
161 | |||
162 | for (ctran = s->transitions_head; NULL != ctran; ctran = ctran->next) | ||
163 | { | ||
164 | if (NULL == ctran->to_state) | ||
165 | { | ||
166 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
167 | "Transition from State %i has no state for transitioning\n", | ||
168 | s->id); | ||
169 | continue; | ||
170 | } | ||
171 | |||
172 | if (ctran->label == 0) | ||
173 | { | ||
174 | GNUNET_asprintf (&s_tran, | ||
175 | "\"%s(%i)\" -> \"%s(%i)\" [label = \"epsilon\", color=\"0.%i 0.8 0.95\"];\n", | ||
176 | s->name, s->proof_id, ctran->to_state->name, | ||
177 | ctran->to_state->proof_id, s->scc_id); | ||
178 | } | ||
179 | else | ||
180 | { | ||
181 | GNUNET_asprintf (&s_tran, | ||
182 | "\"%s(%i)\" -> \"%s(%i)\" [label = \"%c\", color=\"0.%i 0.8 0.95\"];\n", | ||
183 | s->name, s->proof_id, ctran->to_state->name, | ||
184 | ctran->to_state->proof_id, ctran->label, s->scc_id); | ||
185 | } | ||
186 | |||
187 | if (NULL == s_tran) | ||
188 | { | ||
189 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print state %s\n", | ||
190 | s->name); | ||
191 | return; | ||
192 | } | ||
193 | |||
194 | fwrite (s_tran, strlen (s_tran), 1, p); | ||
195 | GNUNET_free (s_tran); | ||
196 | s_tran = NULL; | ||
197 | } | ||
198 | } | ||
199 | |||
200 | |||
201 | /** | ||
202 | * Save the given automaton as a GraphViz dot file | ||
203 | * | ||
204 | * @param a the automaton to be saved | ||
205 | * @param filename where to save the file | ||
206 | */ | ||
207 | void | ||
208 | GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a, | ||
209 | const char *filename) | ||
210 | { | ||
211 | char *start; | ||
212 | char *end; | ||
213 | FILE *p; | ||
214 | |||
215 | if (NULL == a) | ||
216 | { | ||
217 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not print NFA, was NULL!"); | ||
218 | return; | ||
219 | } | ||
220 | |||
221 | if (NULL == filename || strlen (filename) < 1) | ||
222 | { | ||
223 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No Filename given!"); | ||
224 | return; | ||
225 | } | ||
226 | |||
227 | p = fopen (filename, "w"); | ||
228 | |||
229 | if (NULL == p) | ||
230 | { | ||
231 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not open file for writing: %s", | ||
232 | filename); | ||
233 | return; | ||
234 | } | ||
235 | |||
236 | /* First add the SCCs to the automaton, so we can color them nicely */ | ||
237 | scc_tarjan (a); | ||
238 | |||
239 | start = "digraph G {\nrankdir=LR\n"; | ||
240 | fwrite (start, strlen (start), 1, p); | ||
241 | |||
242 | GNUNET_REGEX_automaton_traverse (a, &GNUNET_REGEX_automaton_save_graph_step, | ||
243 | p); | ||
244 | |||
245 | end = "\n}\n"; | ||
246 | fwrite (end, strlen (end), 1, p); | ||
247 | fclose (p); | ||
248 | } | ||