How to linearize a binary and-or graph in C#?

Question

I try to 'linearize' every possibilities of a binary and-or tree to make it more easily readable. Every possibilities should be added to the following structure :

// (x1 AND x2) OR (x2 AND x3)
List<List<Node>> possibilities = new List<List<Node>>() {
    { x1, x2 },
    { x2, x3 }
};

I'm facing some difficulties to generate the list-based possibilities from a tree structure. A simplified version or my algorithm which doesn't return a correct answer in many case is:

class TreeDecomposer {
    public List<TreePath> Possibilities = new List<TreePath>();
    // TreePath = { List<TreeNode> path, bool IsAdded }

    public TreeDecomposer(AbstractTree tree) {
        DecomposeTree(tree, new TreePath());
    }

    public void DecomposeTree(AbstractTree tree, TreePath path)
    {
        // Add the path to the list of possibilities
        if (!path.IsAdded)
        {
            Possibilities.Add(path);
            path.IsAdded = true;
        }

        // Recursive browse
        if (tree is TreeConnector) {
            TreeConnector treeConnector = (TreeConnector)tree;
            if (treeConnector.Connection == "&")
            {
                DecomposeTree(treeConnector.LeftTree, path);
                DecomposeTree(treeConnector.RightTree, path);
            }
            else if (treeConnector.Connection == "|")
            {
                TreePath clonedPath = (TreePath)path.Clone(); // deep clone

                DecomposeTree(treeConnector.LeftTree, path);
                DecomposeTree(treeConnector.RightTree, clonedPath); // somehow 'or' operator multiplies possibilities by two?
            }
        }

        // Leaf
        else if (tree is TreeValue) {
            TreeValue treeValue = (TreeValue)tree;
            path.Add(treeValue);
        }
    }
}

I need help to find the correct algorithm working with my tree structure to browse the tree and construct every possibitilies of 'AND-path'.

Two basic example:

Binary end-or tree example (1)

Formula: (a | b) & (c | d)
Possibilities:

{
    {a, c}, // or {c, a}, the order doesn't matter
    {a, d},
    {b, c},
    {b, d}
}

Binary end-or tree example (2)

Formula: a & ((b | c) & d)
Possibilities:

{
    {a, b, d}, // or {d, b, a}, the order doesn't matter
    {a, c, d}
}

Tree structure:

The implementation or the Tree structure is the following:

abstract class AbstractTree {}

class TreeConnector: AbstractTree
{
    public string Connection; // '&' or '|'
    public AbstractTree LeftTree;
    public AbstractTree RightTree;
}

class TreeValue : AbstractTree
{
    public string Data; // 'a', or 'b', ...
}

Thanks a lot for your help.

Answer 1

Based on @Freggar link, here is a simplified implementation of the 'OR' distribution. It's probably not done in the most efficient way, but it gives a global idea of what I was looking for.

/*
    TreePath = {
        HashSet<TreeNode> path,
        bool IsAdded // set to false even if it's true when an instance is cloned
    }

    Every class (Tree...) define the methods:
        public object Clone()
        public bool Equals(T typedObj)
        public override bool Equals(object obj)
        public override int GetHashCode()
*/

enum TreeBranch
{
    Unknown,
    Left,
    Right
}

class TreeDecomposer {
    public List<TreePath> Possibilities = new List<TreePath>();

    public TreeDecomposer(AbstractTree tree)
    {
        DecomposeTree(null, tree, TreeBranch.Unknown, new TreePath());
        RemoveDuplicatePaths();
    }

    public void DecomposeTree(AbstractTree parentNode, AbstractTree node, TreeBranch branch, TreePath path)
    {
        if (!path.IsAdded)
        {
            Possibilities.Add(path);
            path.IsAdded = true;
        }

        // Recursive browse
        if (node is TreeConnector) {
                TreeConnector treeConnector = (TreeConnector)node;
                if (treeConnector.Connection == "&")
                {
                    DecomposeTree(treeConnector, treeConnector.LeftTree, TreeBranch.Left, path);
                    DecomposeTree(treeConnector, treeConnector.RightTree, TreeBranch.Right, path);
                }
                else if (treeConnector.Connection == "|")
                {
                    // In this case, parentNode is a TreeOperator
                    if (parentNode != null)
                    {
                        // Left distribution
                        TreePath clonedPathLeftDistribution = (TreePath)path.Clone();
                        TreeConnector parentTreeConnectorLeftDistribution = (TreeConnector)parentNode.Clone();

                        // Right distribution
                        TreePath clonedPathRightDistribution = (TreePath)path.Clone();
                        TreeConnector parentTreeConnectorRightDistribution = (TreeConnector)parentNode.Clone();

                        if (branch == TreeBranch.Left)
                        {
                            parentTreeConnectorLeftDistribution.LeftTree = treeConnector.LeftTree;
                            parentTreeConnectorRightDistribution.LeftTree = treeConnector.RightTree;
                        }
                        else if (branch == TreeBranch.Right)
                        {
                            parentTreeConnectorLeftDistribution.RightTree = treeConnector.LeftTree;
                            parentTreeConnectorRightDistribution.RightTree = treeConnector.RightTree;
                        }

                        // Remove obsolete path
                        Possibilities.Remove(path);

                        // Browse recursively distributed tree ; the path must be different (by ref) if the parent operator is 'OR'
                        DecomposeTree(
                            parentTreeConnectorLeftDistribution,
                            parentTreeConnectorLeftDistribution.LeftTree,
                            TreeBranch.Left,
                            parentTreeConnectorLeftDistribution.Connection == "|"
                                ? (TreePath)clonedPathLeftDistribution.Clone()
                                : clonedPathLeftDistribution
                        );
                        DecomposeTree(
                            parentTreeConnectorLeftDistribution,
                            parentTreeConnectorLeftDistribution.RightTree,
                            TreeBranch.Right,
                            clonedPathLeftDistribution
                        );

                        DecomposeTree(
                            parentTreeConnectorRightDistribution,
                            parentTreeConnectorRightDistribution.LeftTree,
                            TreeBranch.Left,
                            parentTreeConnectorLeftDistribution.Connection == "|"
                                ? (TreePath)clonedPathRightDistribution.Clone()
                                : clonedPathRightDistribution
                        );
                        DecomposeTree(
                            parentTreeConnectorRightDistribution,
                            parentTreeConnectorRightDistribution.RightTree,
                            TreeBranch.Right,
                            clonedPathRightDistribution
                        );
                    }
                    // The operator is the root of the tree; we simply divide the path
                    else
                    {
                        TreePath clonedLeftPath = (TreePath)path.Clone();
                        TreePath clonedRightPath = (TreePath)path.Clone();

                        // Remove obsolete path
                        Possibilities.Remove(path);

                        DecomposeTree(treeConnector, treeConnector.LeftTree, TreeBranch.Left, clonedLeftPath);
                        DecomposeTree(treeConnector, treeConnector.RightTree, TreeBranch.Right, clonedRightPath);
                    }
                }
                break;
        }

        // Leaf
        else if (node is TreeValue) {
            TreeValue treeValue = (TreeValue)node;
            path.Add(treeValue);
        }
    }

    public void RemoveDuplicatePaths()
    {
        Possibilities = Possibilities.Distinct().ToList();
    }
}

Note:

Here, I want to keep only the unique possibilities; that's why I use HashSet instead of List:

• "a & a & b" => "a & b"

The method RemoveDuplicatePaths is used to remove duplicated combinations:

• "a & b" and "b & a" are both the same possibility (regarding the truth value)