Recherche dans une arborescence à l'aide de LINQ

J'ai un arbre créé à partir de cette classe.

class Node
{
    public string Key { get; }
    public List<Node> Children { get; }
}

Je veux rechercher dans tous les enfants et tous leurs enfants pour obtenir ceux qui correspondent à une condition:

node.Key == SomeSpecialKey

Comment puis-je l'implémenter?

C'est une idée fausse que cela nécessite une récursivité. Il va avoir besoin d' une pile ou une file d' attente et le plus simple est de mettre en œuvre à l'aide de la récursivité. Par souci d'exhaustivité, je vais fournir une réponse non récursive.

static IEnumerable<Node> Descendants(this Node root)
{
    var nodes = new Stack<Node>(new[] {root});
    while (nodes.Any())
    {
        Node node = nodes.Pop();
        yield return node;
        foreach (var n in node.Children) nodes.Push(n);
    }
}

Utilisez cette expression par exemple pour l'utiliser:

root.Descendants().Where(node => node.Key == SomeSpecialKey)

Recherche dans une arborescence d'objets avec Linq

public static class TreeToEnumerableEx
{
    public static IEnumerable<T> AsDepthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> childrenFunc)
    {
        yield return head;

        foreach (var node in childrenFunc(head))
        {
            foreach (var child in AsDepthFirstEnumerable(node, childrenFunc))
            {
                yield return child;
            }
        }

    }

    public static IEnumerable<T> AsBreadthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> childrenFunc)
    {
        yield return head;

        var last = head;
        foreach (var node in AsBreadthFirstEnumerable(head, childrenFunc))
        {
            foreach (var child in childrenFunc(node))
            {
                yield return child;
                last = child;
            }
            if (last.Equals(node)) yield break;
        }

    }
}

Si vous souhaitez conserver une syntaxe similaire à Linq, vous pouvez utiliser une méthode pour obtenir tous les descendants (enfants + enfants enfants, etc.)

static class NodeExtensions
{
    public static IEnumerable<Node> Descendants(this Node node)
    {
        return node.Children.Concat(node.Children.SelectMany(n => n.Descendants()));
    }
}

Cet énumérable peut ensuite être interrogé comme tout autre en utilisant where ou first ou autre.

Vous pouvez essayer cette méthode d'extension pour énumérer les nœuds de l'arborescence:

static IEnumerable<Node> GetTreeNodes(this Node rootNode)
{
    yield return rootNode;
    foreach (var childNode in rootNode.Children)
    {
        foreach (var child in childNode.GetTreeNodes())
            yield return child;
    }
}

Ensuite, utilisez cela avec une Where()clause:

var matchingNodes = rootNode.GetTreeNodes().Where(x => x.Key == SomeSpecialKey);

Peut-être avez-vous juste besoin

node.Children.Where(child => child.Key == SomeSpecialKey)

Ou, si vous avez besoin de rechercher un niveau plus profond,

node.Children.SelectMany(
        child => child.Children.Where(child => child.Key == SomeSpecialKey))

Si vous devez effectuer une recherche à tous les niveaux, procédez comme suit:

IEnumerable<Node> FlattenAndFilter(Node source)
{
    List<Node> l = new List();
    if (source.Key == SomeSpecialKey)
        l.Add(source);
    return
        l.Concat(source.Children.SelectMany(child => FlattenAndFilter(child)));
}

public class Node
    {
        string key;
        List<Node> children;

        public Node(string key)
        {
            this.key = key;
            children = new List<Node>();
        }

        public string Key { get { return key; } }
        public List<Node> Children { get { return children; } }

        public Node Find(Func<Node, bool> myFunc)
        {
            foreach (Node node in Children)
            {
                if (myFunc(node))
                {
                    return node;
                }
                else 
                {
                    Node test = node.Find(myFunc);
                    if (test != null)
                        return test;
                }
            }

            return null;
        }
    }

Et puis vous pouvez rechercher comme:

    Node root = new Node("root");
    Node child1 = new Node("child1");
    Node child2 = new Node("child2");
    Node child3 = new Node("child3");
    Node child4 = new Node("child4");
    Node child5 = new Node("child5");
    Node child6 = new Node("child6");
    root.Children.Add(child1);
    root.Children.Add(child2);
    child1.Children.Add(child3);
    child2.Children.Add(child4);
    child4.Children.Add(child5);
    child5.Children.Add(child6);

    Node test = root.Find(p => p.Key == "child6");

Pourquoi ne pas utiliser une IEnumerable<T>méthode d'extension

public static IEnumerable<TResult> SelectHierarchy<TResult>(this IEnumerable<TResult> source, Func<TResult, IEnumerable<TResult>> collectionSelector, Func<TResult, bool> predicate)
{
    if (source == null)
    {
        yield break;
    }
    foreach (var item in source)
    {
        if (predicate(item))
        {
            yield return item;
        }
        var childResults = SelectHierarchy(collectionSelector(item), collectionSelector, predicate);
        foreach (var childItem in childResults)
        {
            yield return childItem;
        }
    }
}

alors fais juste ça

var result = nodes.Children.SelectHierarchy(n => n.Children, n => n.Key.IndexOf(searchString) != -1);

Il y a quelque temps, j'ai écrit un article sur le projet de code qui décrit comment utiliser Linq pour interroger des structures arborescentes:

http://www.codeproject.com/KB/linq/LinqToTree.aspx

Cela fournit une API de style linq-to-XML où vous pouvez rechercher des descendants, des enfants, des ancêtres, etc.

Probablement exagéré pour votre problème actuel, mais pourrait intéresser les autres.

Vous pouvez utiliser cette méthode d'extension pour interroger l'arborescence.

    public static IEnumerable<Node> InTree(this Node treeNode)
    {
        yield return treeNode;

        foreach (var childNode in treeNode.Children)
            foreach (var flattendChild in InTree(childNode))
                yield return flattendChild;
    }

J'ai une méthode d'extension générique qui peut aplatir n'importe lequel IEnumerable<T>et à partir de cette collection aplatie, vous pouvez obtenir le nœud que vous voulez.

public static IEnumerable<T> FlattenHierarchy<T>(this T node, Func<T, IEnumerable<T>> getChildEnumerator)
{
    yield return node;
    if (getChildEnumerator(node) != null)
    {
        foreach (var child in getChildEnumerator(node))
        {
            foreach (var childOrDescendant in child.FlattenHierarchy(getChildEnumerator))
            {
                yield return childOrDescendant;
            }
        }
    }
}

Utilisez ceci comme ceci:

var q = from node in myTree.FlattenHierarchy(x => x.Children)
        where node.Key == "MyKey"
        select node;
var theNode = q.SingleOrDefault();

J'utilise les implémentations suivantes pour énumérer les éléments de l'arborescence

    public static IEnumerable<Node> DepthFirstUnfold(this Node root) =>
        ObjectAsEnumerable(root).Concat(root.Children.SelectMany(DepthFirstUnfold));

    public static IEnumerable<Node> BreadthFirstUnfold(this Node root) {
        var queue = new Queue<IEnumerable<Node>>();
        queue.Enqueue(ObjectAsEnumerable(root));

        while (queue.Count != 0)
            foreach (var node in queue.Dequeue()) {
                yield return node;
                queue.Enqueue(node.Children);
            }
    }

    private static IEnumerable<T> ObjectAsEnumerable<T>(T obj) {
        yield return obj;
    }

BreadthFirstUnfold dans l'implémentation ci-dessus utilise la file d'attente des séquences de nœuds au lieu de la file d'attente des nœuds. Ce n'est pas une manière classique d'algorithme BFS.

Et juste pour le plaisir (presque une décennie plus tard) une réponse utilisant également des génériques mais avec une boucle Stack et While, basée sur la réponse acceptée par @vidstige.

public static class TypeExtentions
{

    public static IEnumerable<T> Descendants<T>(this T root, Func<T, IEnumerable<T>> selector)
    {
        var nodes = new Stack<T>(new[] { root });
        while (nodes.Any())
        {
            T node = nodes.Pop();
            yield return node;
            foreach (var n in selector(node)) nodes.Push(n);
        }
    }

    public static IEnumerable<T> Descendants<T>(this IEnumerable<T> encounter, Func<T, IEnumerable<T>> selector)
    {
        var nodes = new Stack<T>(encounter);
        while (nodes.Any())
        {
            T node = nodes.Pop();
            yield return node;
            if (selector(node) != null)
                foreach (var n in selector(node))
                    nodes.Push(n);
        }
    }
}

Étant donné une collection, on peut utiliser comme ça

        var myNode = ListNodes.Descendants(x => x.Children).Where(x => x.Key == SomeKey);

ou avec un objet racine

        var myNode = root.Descendants(x => x.Children).Where(x => x.Key == SomeKey);