GNUnet  0.10.x
Data Structures | Functions
regex_test_graph.c File Reference

functions for creating .dot graphs from regexes More...

#include "platform.h"
#include "regex_internal_lib.h"
#include "regex_test_lib.h"
#include "regex_internal.h"
Include dependency graph for regex_test_graph.c:

Go to the source code of this file.

Data Structures

struct  REGEX_TEST_Graph_Context
 Context for graph creation. More...
 

Functions

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 from 'v'. More...
 
static void scc_tarjan (struct REGEX_INTERNAL_Automaton *a)
 Detect all SCCs (Strongly Connected Components) inside the given automaton. More...
 
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. More...
 
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. More...
 

Detailed Description

functions for creating .dot graphs from regexes

Author
Maximilian Szengel

Definition in file regex_test_graph.c.

Function Documentation

◆ scc_tarjan_strongconnect()

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 
)
static

Recursive function doing DFS with 'v' as a start, detecting all SCCs inside the subgraph reachable from 'v'.

Used with scc_tarjan function to detect all SCCs inside an automaton.

Parameters
scc_countercounter for numbering the sccs
vstart vertex
indexcurrent index
stackstack for saving all SCCs
stack_sizecurrent size of the stack

Definition at line 65 of file regex_test_graph.c.

References REGEX_INTERNAL_State::contained, REGEX_INTERNAL_State::index, REGEX_INTERNAL_State::lowlink, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::scc_id, t, REGEX_INTERNAL_Transition::to_state, and REGEX_INTERNAL_State::transitions_head.

Referenced by scc_tarjan().

69 {
70  struct REGEX_INTERNAL_State *w;
72 
73  v->index = *index;
74  v->lowlink = *index;
75  (*index)++;
76  stack[(*stack_size)++] = v;
77  v->contained = 1;
78 
79  for (t = v->transitions_head; NULL != t; t = t->next)
80  {
81  w = t->to_state;
82 
83  if (NULL == w)
84  continue;
85 
86  if (w->index < 0)
87  {
88  scc_tarjan_strongconnect(scc_counter, w, index, stack, stack_size);
89  v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink;
90  }
91  else if (1 == w->contained)
92  v->lowlink = (v->lowlink > w->index) ? w->index : v->lowlink;
93  }
94 
95  if (v->lowlink == v->index)
96  {
97  (*scc_counter)++;
98  do
99  {
100  w = stack[--(*stack_size)];
101  w->contained = 0;
102  w->scc_id = *scc_counter;
103  }
104  while (w != v);
105  }
106 }
unsigned int scc_id
Marking the state as part of an SCC (Strongly Connected Component).
int index
Used for SCC detection.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
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 &#39;v&#39; as a start, detecting all SCCs inside the subgraph reachable fr...
int contained
Marking the state as contained.
static struct GNUNET_SCHEDULER_Task * t
Main task.
Transition between two states.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
int lowlink
Used for SCC detection.
Here is the caller graph for this function:

◆ scc_tarjan()

static void scc_tarjan ( struct REGEX_INTERNAL_Automaton a)
static

Detect all SCCs (Strongly Connected Components) inside the given automaton.

SCCs will be marked using the scc_id on each state.

Parameters
athe automaton for which SCCs should be computed and assigned.

Definition at line 116 of file regex_test_graph.c.

References REGEX_INTERNAL_State::contained, REGEX_INTERNAL_State::index, REGEX_INTERNAL_State::lowlink, REGEX_INTERNAL_State::next, scc_tarjan_strongconnect(), REGEX_INTERNAL_Automaton::state_count, and REGEX_INTERNAL_Automaton::states_head.

Referenced by REGEX_TEST_automaton_save_graph().

117 {
118  unsigned int index;
119  unsigned int scc_counter;
120  struct REGEX_INTERNAL_State *v;
121  struct REGEX_INTERNAL_State *stack[a->state_count];
122  unsigned int stack_size;
123 
124  for (v = a->states_head; NULL != v; v = v->next)
125  {
126  v->contained = 0;
127  v->index = -1;
128  v->lowlink = -1;
129  }
130 
131  stack_size = 0;
132  index = 0;
133  scc_counter = 0;
134 
135  for (v = a->states_head; NULL != v; v = v->next)
136  {
137  if (v->index < 0)
138  scc_tarjan_strongconnect(&scc_counter, v, &index, stack, &stack_size);
139  }
140 }
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * states_head
DLL of states.
int index
Used for SCC detection.
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 &#39;v&#39; as a start, detecting all SCCs inside the subgraph reachable fr...
int contained
Marking the state as contained.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
int lowlink
Used for SCC detection.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ REGEX_TEST_automaton_save_graph_step()

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.

cls is expected to be a file pointer to an open file. Used only in conjunction with REGEX_TEST_automaton_save_graph.

Parameters
clsfile pointer.
countcurrent count of the state, not used.
sstate.

Definition at line 153 of file regex_test_graph.c.

References REGEX_INTERNAL_State::accepting, REGEX_TEST_Graph_Context::coloring, ctx, REGEX_INTERNAL_State::dfs_id, REGEX_TEST_Graph_Context::filep, GNUNET_asprintf(), GNUNET_assert, GNUNET_ERROR_TYPE_ERROR, GNUNET_free, GNUNET_h2s(), GNUNET_log, GNUNET_YES, REGEX_INTERNAL_State::hash, REGEX_INTERNAL_State::id, REGEX_INTERNAL_Transition::label, name, REGEX_INTERNAL_State::name, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::proof, REGEX_INTERNAL_State::scc_id, REGEX_INTERNAL_Transition::to_state, REGEX_INTERNAL_State::transitions_head, and REGEX_TEST_Graph_Context::verbose.

Referenced by REGEX_TEST_automaton_save_graph().

155 {
156  struct REGEX_TEST_Graph_Context *ctx = cls;
157  struct REGEX_INTERNAL_Transition *ctran;
158  char *s_acc = NULL;
159  char *s_tran = NULL;
160  char *name;
161  char *to_name;
162 
163  if (GNUNET_YES == ctx->verbose)
164  GNUNET_asprintf(&name, "%i (%s) (%s) (%s)", s->dfs_id, s->name, s->proof,
165  GNUNET_h2s(&s->hash));
166  else
167  GNUNET_asprintf(&name, "%i", s->dfs_id);
168 
169  if (s->accepting)
170  {
171  if (GNUNET_YES == ctx->coloring)
172  {
173  GNUNET_asprintf(&s_acc,
174  "\"%s\" [shape=doublecircle, color=\"0.%i 0.8 0.95\"];\n",
175  name, s->scc_id * s->scc_id);
176  }
177  else
178  {
179  GNUNET_asprintf(&s_acc, "\"%s\" [shape=doublecircle];\n", name,
180  s->scc_id);
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, s->scc_id);
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, s->scc_id);
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, s->scc_id);
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 }
unsigned int scc_id
Marking the state as part of an SCC (Strongly Connected Component).
FILE * filep
File pointer to the dot file used for output.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
Context for graph creation.
struct GNUNET_HashCode hash
Hash of the state.
int accepting
If this is an accepting state or not.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
char * proof
Proof for this state.
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
int GNUNET_asprintf(char **buf, const char *format,...)
Like asprintf, just portable.
int coloring
Coloring flag, if set to GNUNET_YES SCCs will be colored.
char * name
Human readable name of the state.
Transition between two states.
int verbose
Verbose flag, if it&#39;s set to GNUNET_YES additional info will be printed in the graph.
const char * name
unsigned int dfs_id
Linear state ID accquired by depth-first-search.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
#define GNUNET_log(kind,...)
char * label
Label for this transition.
#define GNUNET_YES
Definition: gnunet_common.h:77
unsigned int id
Unique state id.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ REGEX_TEST_automaton_save_graph()

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.

Parameters
athe automaton to be saved.
filenamewhere to save the file.
optionsoptions for graph generation that include coloring or verbose mode

Definition at line 270 of file regex_test_graph.c.

References REGEX_TEST_Graph_Context::coloring, end, REGEX_TEST_Graph_Context::filep, GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_NO, GNUNET_YES, REGEX_INTERNAL_automaton_traverse(), REGEX_TEST_automaton_save_graph_step(), REGEX_TEST_GRAPH_COLORING, REGEX_TEST_GRAPH_VERBOSE, scc_tarjan(), start, REGEX_INTERNAL_Automaton::start, and REGEX_TEST_Graph_Context::verbose.

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 }
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
Context for graph creation.
struct GNUNET_GETOPT_CommandLineOption options[]
Definition: 002.c:5
The generated graph will include extra information such as the NFA states that were used to generate ...
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
#define GNUNET_NO
Definition: gnunet_common.h:78
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
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&#39;s start state, visiting all reachable states and calling &#39;action&#39; on each one of them.
static char * filename
Enable graph coloring.
struct REGEX_INTERNAL_State * start
First state of the automaton.
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(struct REGEX_INTERNAL_Automaton *a)
Detect all SCCs (Strongly Connected Components) inside the given automaton.
#define GNUNET_log(kind,...)
#define GNUNET_YES
Definition: gnunet_common.h:77
Here is the call graph for this function: