[gecode-users] Initialization of internal tree nodes in the unary Edge Finding propagator

[Roberto Castañeda]

Hello, everyone!

I am studying the propagation algorithms for unary resource constraints from 
Petr Vilím [1], and looking at how they are implemented in Gecode 3.4.0. While 
looking at the implementation of the Edge Finding algorithm (scheduling/unary/edge-finding.hpp),
I have found a discrepancy with respect to Algorithm 2.6 in [1] that I do not
really understand: in the Gecode implementation, the internal nodes of the 
Theta-Lambda tree are not initialized (i.e. assigned values for p, ect, lp, lect
 computed from the leaves upwards) at the beginning of the algorithm. 

I have also checked if this makes any difference on the propagation for the root 
search node for the example from Figure 2.4. [1]. This is the frequency of execution
of each propagator before reaching the fixpoint with the original Gecode Edge Finding 
algorithm:

6 Detectable Precedences
6 Edge Finding
6 Not-First/Not-Last
3 Overload Checking
3 Subsumed

And this is the frequency when I initialized all nodes at the beginning (with time 
complexity O(n)):

4 Detectable Precedences
4 Edge Finding
4 Not-First/Not-Last
2 Overload Checking
2 Subsumed

While the constraint stores in the fixpoint are equal in both cases, the second version
(which I believe is what [1] proposes) saves one iteration of the whole family of unary
resource propagators. Is there any reason I missed for not initializing the internal 
nodes of the Theta-Lambda tree?

I attach the Figure 2.4. example code.

Best regards,

Roberto

[1] Petr Vilím, Global Constraints in Scheduling, PhD thesis, 
Charles University, Prague, Czech Republic, 2007.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: figure_2_4.cpp
Type: application/octet-stream
Size: 1243 bytes
Desc: figure_2_4.cpp
URL: <http://www.gecode.org/pipermail/users/attachments/20100924/0d930943/attachment.obj>