Problem with consecutive ones

[martinlackner]

The consecutive ones instance

0,1,0,0,0,0,0,1,0,0,0 0,0,1,0,0,0,0,0,0,0,1 0,1,1,0,0,0,0,0,0,1,0 0,1,1,0,1,0,0,1,1,1,1

is a yes-instance; the correct order is [0, 3, 5, 6, 4, 8, 7, 1, 9, 2, 10].

from tryalgo import pq_tree as pq
pq.consecutive_ones_property([{1,2,9},{1,7},{2,10},{1,2,9},{1,2,4,7,8,9,10}],{0,1,2,3,4,5,6,7,8,9,10}) 

gives this correct output. However, when permuting the input,

pq.consecutive_ones_property([{1,7},{2,10},{1,2,9},{1,2,4,7,8,9,10}],{0,1,2,3,4,5,6,7,8,9,10}) 

fails with an error message:

 Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/martin/.local/lib/python3.6/site-packages/tryalgo/pq_tree.py", line 268, in consecutive_ones_property
    tree.reduce(S)
  File "/home/martin/.local/lib/python3.6/site-packages/tryalgo/pq_tree.py", line 235, in reduce
    z.full_leafs += x.full_leafs                 # cumulate bottom up full leaf numbers
AttributeError: 'NoneType' object has no attribute 'full_leafs'

[jilljenn]

Thanks! We acknowledge your message and will fix it.

[xtof-durr]

Ja Mist aber auch. Danke für die Nachricht. Wir gucken uns das diese Woche an and sagen Bescheid. — christoph

[martinlackner]

Thanks a lot for looking into this!

We would like to use this algorithm for experiments in a journal submission. Do you have an estimate when you will be able to fix the problem?

Best regards Martin

[xtof-durr]

Dear Martin,

we corrected the bug you found. It was a missing instruction in template P6 of the reduce function. Thank you very much. I guess our test bed did not covered all branches of the code. The corrected code for PQ-trees is in this github, but not yet in the tryalgo package. We will make a new release soon.

Thank you that you reported this bug, and we wish you luck with your journal submission.

Best regards, Christoph

[xtof-durr]

Dear Martin,

we are writing more tests right to cover 100% of the pq_tree code. Maybe it would be better for you meanwhile to use a different implementation of the data structure. But we hope to fix it in a few days.

Best regards, Christoph

[martinlackner]

Hi Christoph

Thanks for the updates!

It seems that there is still a bug in the current version. The following instance should be a yes-instance with the ordering [0,1,2,3,4,5]. It appears that the second {0, 1, 2, 3, 4, 5} constraint in the list causes problems.

import tryalgo.pq_tree as pq_tree
constraints = [{1, 2, 3, 4, 5}, {0, 1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}, {3, 4}, {3, 4}, {1, 2, 3, 4, 5}, {1, 2}, {0, 1, 2, 3, 4}, {2}, {1, 2, 3}, {1, 2, 3, 4}, {0, 1, 2, 3, 4, 5}, {1}, {0, 1, 2}, {0, 1, 2}, {0, 1, 2, 3}, {0, 1, 2, 3, 4}, {0, 1, 2, 3, 4, 5}, {0, 1}, {0}, {0, 1, 2}, {0, 1, 2, 3}, {0, 1, 2, 3, 4}, {0, 1, 2, 3, 4, 5}]
for i in range(1, len(constraints)):
    print(i, constraints[i-1], pq_tree.consecutive_ones_property(constraints[:i]))

For our paper, we have decided to use a SAT solver for consecutive ones. This is quite fast and straight-forward to implement.

Best Martin

[xtof-durr]

Hello Martin,

thank you for your counter examples. This gets so embarrassing. It is quite a difficult data structure to implement. I will give another try, and if I don't succeed, possibly implement lexBFS, which is simpler. I cannot do it in next future, but it seems that it is not urgent, since you used a different tool now.

Best wishes, Christoph

[martinlackner]

It is quite a difficult data structure to implement.

Yes, that seems to be the case. Actually lots of available PQ trees implementation mention that there seem to be some borderline cases that do not work. (In that sense it would be very nice to have a trustworthy PQ implementation - but LexBFS might be an even better solution.)

For our project it's not urgent. The SAT approach worked sufficiently well for our purpose. Maybe this approach could also help in verifying test cases.

Good luck fixing the bug! Martin