Hi Coby, Uff, that's really a hard one and I do not really have an answer. The key point is that the layered graph as constructed by initialize cannot be used really standalone. The data structure essentially makes three key assumptions: 1. The variable domains are restricted as done in the ::post() member function. 2. When the data structure is copied you do it as done the ::LayeredGraph constructor (the additional steps in the ::copy() meber function are really only optimizations of the data structure but not crucial). 3. Any changes to the data structure are done as implemented by ::advise() and ::propagate() together. Only their combination make sure that the data structure's invariants hold.
I do not know how much reading you already did in the Part P of MPG but you will have to read and understand pretty much all of it. The problem is really that the implementation is highly optimized and has pretty tricky invariants to maintain. The level of documentation is barely enough for me ;-) Sorry that I do not have to offer something more helpful than this. All the best Christian -- Christian Schulte, www.gecode.org/~schulte Professor of Computer Science, KTH, cschu...@kth.se Expert Researcher, SICS, cschu...@sics.se -----Original Message----- From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf Of Coby Viner Sent: Wednesday, December 23, 2015 12:26 AM To: users@gecode.org Subject: [gecode-users] Usage of layered graphs, without regard for propagation, and audit failure 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 b y 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 _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
