Как линеаризовать двоичный и / или граф в C#?

Question

Я стараюсь "линеаризовать" все возможности двоичного и / или дерева, чтобы сделать его более читабельным. Все возможности должны быть добавлены к следующей структуре:

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

Я столкнулся с некоторыми трудностями при создании возможностей на основе списка из древовидной структуры. Упрощенная версия или мой алгоритм, который во многих случаях не дает правильного ответа:

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);
        }
    }
}

Мне нужна помощь, чтобы найти правильный алгоритм, работающий с моей древовидной структурой, чтобы просмотреть дерево и построить все возможные варианты "И-пути".

Два основных примера:

Пример двоичного конца или дерева (1)

Формула: (a | b) & (c | d)
Возможности:

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

Пример двоичного конца или дерева (2)

Формула: a & ((b | c) & d)
Возможности:

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

Древовидная структура:

Реализация или древовидная структура следующие:

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', ...
}

Спасибо большое за вашу помощь.

Answer 1

На основе ссылки @Freggar приведена упрощенная реализация дистрибутива 'OR'. Вероятно, это сделано не самым эффективным способом, но дает общее представление о том, что я искал.

/*
    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();
    }
}

Примечание:

Здесь я хочу сохранить только уникальные возможности; вот почему я использую HashSet вместо List:

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

Метод RemoveDuplicatePaths используется для удаления дублированных комбинаций:

• "a & b" и "b & a" - одна и та же возможность (относительно значения истинности)