I'm trying to convert a binary tree e.g.
OR (Implementation of Operator - a specialisation of TreeNode... see below)
|-A (Implementation of TreeNode... see below)
|-OR
|-B
|-AND (Implementation of Operator - a specialisation of TreeNode... see below)
|-C
|-OR
|-D
|-E
into it's equivalent Conjunctive Normal Form (CND) representation. I believe that because I'm only using the logical OR + AND operators that the only step I'd have to perform is the distribution of AND over OR. This would produce the following tree (still binary for my purposes) in CNF:
AND
|-OR
| |-A
| |-OR
| |-B
| |-OR
| |-E
| |-D
|-OR
|-A
|-OR
|-B
|-OR
|-E
|-C
I'm having issues creating an algorithm to do this... so far I have the following skeleton which will re-write the tree bottom up (Notice the recursive call to reconstruct):
public TreeNode reconstruct(TreeNode treeNode) {
if(treeNode instanceof Operator) {
TreeNode left = reconstruct(((Operator)treeNode).getLeft());
TreeNode right = reconstruct(((Operator)treeNode).getRight());
return distribute(treeNode, left, right);
}
else
return node;
}
Using classes:
-----------
| TreeNode | // Interface
-----------
^
|
-----------
| Operator | // Interface
-----------
| getLeft() |
| getRight()|
| setLeft() |
| setRight()|
-----------
Could anybody suggest an implementation of distribute which would convert to CNF?
// EDIT 1 (After answer from nif)
private Node distribute(TreeNode node, TreeNode left, TreeNode right) {
if (node instanceof Or) {
if (left instanceof And) {
// distribute right over left AND
return
new And(
new Or(((Operator)left).getLeft(), right),
new Or(((Operator)left).getRight(), right)
);
}
else if (right instanceof And) {
// distribute left over right AND
return
new And(
new Or(((Operator)right).getLeft(), left),
new Or(((Operator)right).getRight(), left)
);
}
}
if(node instanceof Operator) {
((Operator)node).setLeft(left);
((Operator)node).setRight(right);
}
// default
return node;
}
If AND and OR are the only operators you are using, it shouldn't be hard to tranform your tree to CNF. All you have to do is find structures in the form OR(AND(X,Y), Z) or OR(Z, AND(X,Y)) and use the distribution law.
private static TreeNode distribute(TreeNode n, TreeNode left, TreeNode right) {
if (n instanceof Or) {
if (left instanceof And) {
// distribute right over left AND
return new And(new Or(left.getLeft(), right),
new Or(left.getRight(), right));
} else if (right instanceof And) {
// distribute left over right AND
return new And(new Or(right.getLeft(), left),
new Or(right.getRight(), left));
}
}
// no change
return treeNode;
}
This algorithm must be applied to all nodes of your tree until the tree isn't changed anymore. The order in which you apply the algorithm to the nodes doesn't matter. Intuitively, repetitive application of the algorithm will pull up all AND nodes over OR nodes until the tree is in CNF.
TreeNode root = ....;
while (true) {
TreeNode transformedRoot = reconstruct(root);
if (root.equals(transformedRoot)) {
break;
}
root = transformedRoot;
}
// root is now in CNF
Note: Be aware that the CNF transformation may blow up your tree exponential in size. The shown implementation is quite primitive and doesn't use any enhancements to reduce computation time.
I recommend you look how the tree is navigated, in your code looks like is a Depth-first search so you will start with the deepest branch (Deepest operator) you have to design your method distribute expecting that order and apply the Distributive Laws for the child nodes in a backtracking way.
A very general description of what distribute method should do is:
The flow of what kind of distributive law have to be applied depends
on parent's operation type and child nodes.
Each child node can be an operator or a value, depending on this combination do the distribution required by the law.
A pseudo code of what i am trying to tell you is:
if parent node is OR type
if child nodes are OPERATOR-VALUE combination
if OPERATION is AND type
apply correspondig distribution
return the new parent
else
apply correspondig distribution
return the new parent
if child node are VALUE-VALUE combination
return parent
if parent node is AND type
if child nodes are OPERATOR-VALUE combination
if OPERATION is AND type
apply correspondig distribution
return the new parent
else
apply correspondig distribution
return the new parent
if child nodes are VALUE-VALUE combination
return parent;
An implementation example:
public TreeNode distribute(TreeNode parent,TreeNode leftChild, TreeNode rightChild) {
if( !(leftChild instanceof Operator) && !(rightChild instanceof Operator) ){
/*There is nothing to do */
return parent;
}
if( parent.getType() == 'OR'){
/*
Apply distributive laws and return the new branch
for example:
*/
if ( (leftChild instanceof operator) && !(rightChild instanceof Operator) ){
TreeNode operatorLeftChild = leftChild.getLeftChild();
TreeNode operatorRightChild = leftChild.getRightChild();
if(leftChild.getType() == 'AND' )
{
/*
Applying distributive laws:
rightChild OR (operatorLeftChild AND operatorRightChild)
-> (rightChild OR operatorLeftChild) AND (rightChild OR operatorRightChild)
*/
TreeNode newBranch = new Operator("AND");
/*new Left child*/
TreeNode newLeftChild= new Operator("OR");
newLeftChild.setLeftChild(rightChild);
newLeftChild.setRightChild(operatorLeftChild);
/*new Richt Child */
TreeNode newRightChild= new Operator("OR");
newRightChild.setLeftChild(rightChild);
newRightChild.setRightChild(operatorRightChild);
/*Setting the new Branch*/
newBranch.setLeftChild(newLeftChild);
newBranch.setRightChild(newRightChild);
return newBranch;
}
}
}
if( parent.getType() == 'AND'){
/*
Else-If and distributive laws stuff
*/
}
/*
You can also implement this part wihtout the else-if code by implementing a true table
but is more abstract and less human redeable
*/
}
Note The previous code has not been tested and i am assuming a lot of things i dont know
how your tree is implemented may be you will be required to update the parent reference in child nodes.
