Dear Gecode Users:
I am working on a project for which (as an initial step) I need to
convert regular expressions to layered graphs, of the form provided by
Gilles Pesant in his 2004 LNCS paper.
For this purpose, I would like to use
Gecode::Int::Extensional::LayeredGraph, constructed from a Gecode
DFA-converted regex. I am able to construct a valid DFA, but am having
some difficulties constructing a layered graph corresponding to it. I
can create the object itself, using the LayeredGraph (Home home, const
VarArgArray< Var > &x, const DFA &dfa) constructor for posting. However,
the resulting graph appears to be invalid.
Upon posting it (via Gecode::Int::Extensional::LayeredGraph< View, Val,
Degree, StateIdx >::LayeredGraph), it appears that I also need to run
Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx
>::initialize, with the same arguments to get a valid initialization of the layered graph (otherwise the pointer assigned to layers is invalid, as are further indices of that array). Once I call initialize, I can access all layers, and there are indeed as many as stated by n (the number of layers). However, the data structures of the layered graph are not consistent. In particular, audit fails on its first assertion (concerning the number of edges). Manual inspection in gdb shows that the numbers reported for total states and edges are way off, both having values of zero, while the actual numbers vastly exceed that (e.g. layer 0 of 11, on support index 2, appears to have 16254 edges and 8880 states). Valgrind shows an error when a call to audit is included, saying that a "Conditional jump or move depends on uninitialised value(s)", but providing no further information other than showing the error originated from the audit call and that the "Uninitialised value was created by a
stack allocation" from the main method itself. Valgrind shows similar errors if n_states
or n_edges are printed from the layered graph. While both erroneously (I assume) output 0,
Valgrind detects memory errors, one similar to the previous one and another referring to the
"Use of uninitialised value of size 8" at the line of code that outputs either
n_states or n_edges.
The documentation on this topic is sparse, and understandably so, since
I am essentially abusing an internal Gecode class for something that it
was not designed for. I was hoping for some guidance on how best to
construct the layered graph corresponding to a DFA, ignoring notions of
propagation or constraint-satisfaction, since I am only interested in
using the layered graph itself.
What would be a reasonable instantiation of the templates: <View, Val,
Degree, StateId> for this purpose? Currently I am using: <Int::IntView,
int, int, int>. Is this a sensible instantiation?
For my purpose, I am attempting to use IntVarArgs that consist of
constant integers (i.e. argument is an IntVar, but with min = max).
These integers correspond to those used in my DFA. Is there any issue
with having such a sequence and is that a valid usage of IntVarArgs?
What would be a good way to simply output the structure of the entire
layered graph in some structured format or for me to access its
components? It appears that I can access the layers easily enough, but
the edges themselves are only temporarily recorded or bound to their
support; is that correct? What would be an idiomatic way of iterating
over the representation of transition variables / state variables?
I apologize if my questions lack precision and would be happy to provide
any necessary clarifications; this is far from my area of expertise.
I would appreciate any pointers or advice that anyone can provide.
Thank you in advance,
Coby Viner
P.S. Congratulations on Gecode's recent 10th birthday!
_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
