corail-research / learning-generic-csp

Representing CP problems as graphs
16 stars 1 forks source link

Implement basic graph reduction #20

Closed jardinetsouffleton closed 1 year ago

jardinetsouffleton commented 1 year ago

In the original graph representation, new operator nodes were created for all appearance of an operator. For example, take a SAT problem. If in a SAT problem there were 4 clauses containing $\neg x_2$, then there would be 4 appearances of the operator $\neg$. Instead, a more compact version would only require one $\neg$ operator and all clauses using $\neg x_2$ would be connected to this one. This achieves the primary aims of the original reduction that was done: reducing the number of nodes and explicitly representing the connection between variable nodes and their negated versions.