One bug detected in the pathConsistency() method

[GoogleCodeExporter]

Hi,

The current implementation of pathConsistency() is not able to know if a new 
constraint edge has been added or not, we need to go through new constraint 
edge one by one.

- What steps will reproduce the problem?
I attached the test case to reproduce the error output.

- What is the expected output? What do you see instead?
In the attached results.txt, we could see the output of the current 
implementation was the first matrix. However, the relation between 2 and 3 
should NOT be Full. Instead, the second matrix was what we expected.

I also attached two images for visualization.

Yi

Original issue reported on code.google.com by luoyi....@gmail.com on 15 Aug 2014 at 9:49

Attachments:

• testcase.txt
• results.txt
• testcase.png
• result.png

[GoogleCodeExporter]

Hi,

thank you for your detailed comments and email! I will soon integrate it!

Best regards,

Jörn

Original comment by jornfra...@gmail.com on 17 Aug 2014 at 6:28

• Changed state: Accepted

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

I also add your changes proposed by you (see also attachment by you):
-----------------------------------
1. In method addConstraint(), I commented out the line:  
//this.addConstraintToConstraintNetwork(constraintAdd);
    I moved this step into pathConsistency() because we have cached all new relations in the modeledConstriants.
2. Replaced your pathConsistency() method with my attached one in the previous 
email.
​
---------------------------------

And another discussion point:
After adding a new dependency/or node you need to execute the path consistency 
algorithm, so theoretically I could also add the following line to 
addConstraint:
this.pathConsistency()

and you answered:
-----
[..] not forget: 
Constraint<E> startConstraint = 
this.modeledConstraints.get(modeledConstraints.size() - 1);
-----

Thank you again, it will soon be updated. 

Original comment by jornfra...@gmail.com on 17 Aug 2014 at 6:33

Attachments:

• pathConsistency.txt

[GoogleCodeExporter]

just one last thing: It seems to be that the output of the original version 
(the boolean return parameter) is in both versions correct if the constraints 
belong only to the ord-horn class of problems.
It is just the constraint network, which could be more reduced (cf. also 
references on completeness). 

An optimization to the aforementioned problem could be to split the constraint 
network in several constraint networks containing only constraints belonging to 
the Ord-Horn Class and run the path consistency algorithm on them. This will be 
part of a future version.

Original comment by jornfra...@gmail.com on 17 Aug 2014 at 6:39

[GoogleCodeExporter]

Original comment by jornfra...@gmail.com on 26 Aug 2014 at 9:17

• Changed state: Started