-
Notifications
You must be signed in to change notification settings - Fork 107
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Problem with consecutive ones #55
Comments
Thanks! We acknowledge your message and will fix it. |
Ja Mist aber auch. Danke für die Nachricht. Wir gucken uns das diese Woche an and sagen Bescheid. — christoph
|
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 |
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
|
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, |
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.
For our paper, we have decided to use a SAT solver for consecutive ones. This is quite fast and straight-forward to implement. Best |
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
|
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! |
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].
gives this correct output. However, when permuting the input,
fails with an error message:
The text was updated successfully, but these errors were encountered: