[gecode-users] Usage of layered graphs, without regard for propagation, and audit failure

[Coby Viner]

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!