How to return a path of nodes from a recursive hierarchy given a condition?

Question

I'm trying to create a linq extension method that returns the path to a selected node.

Path to node Item4 would yield - { Item1, Item2, Item4 }
Path to node Item3 would yield - { Item1, Item3 }

public class Item
{
    public int Id { get; set; }
    public IList<Item> Items { get; set; }
}

Item1
    Item2
        Item4
    Item3

Calling Code

var path = myItem.Items
    .Path(e => e.Items, e => MyPredicateCondition())
    .ToList();

Extension Method

public static IEnumerable<T> Path<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>> childrenSelector,
    Predicate<T> condition)
{
    if (source == null || !source.Any()) return default(T);

    var attempt = source.FirstOrDefault(t => condition(t));
    if (!Equals(attempt, default(T))) return attempt;

    var items = source.SelectMany(childrenSelector)
        .Path(childrenSelector, condition)
        .ToList();

    return attempt;
}

My problem is not finding the actual node, but returning nodes recursively back up the tree to the root node. The data structure should stay how it is - i.e. I don't want the Item referencing it's parent item.

Note: the code currently doesn't compile as I was attempting using IEnumerable yields etc with other ways.

Efficiency is not the issue as it will be used with 3 or 4 levels deep each with just a few items.

Answer 1

Here's a simple Stack-based implementation.

The idea is to put each item that we are going to inspect on a stack, and if it is not part of the path we're looking for, removed it from the stack, until we find the item we're looking for.

IEnumerable<T> Path<T>(IEnumerable<T> source,
                       Func<T, IEnumerable<T>> childrenSelector,
                       Func<T, bool> condition)
{
    var path = new Stack<T>();
    Path(source, childrenSelector, condition, path);
    return path.Reverse().ToList();
}                       
bool Path<T>(IEnumerable<T> source,
             Func<T, IEnumerable<T>> childrenSelector,
             Func<T, bool> condition,
             Stack<T> path)
{
    foreach (var item in source)
    {
        path.Push(item);
        if (condition(item) || Path(childrenSelector(item), childrenSelector, condition, path))
            return true;
        else
            path.Pop();
    }
    return false;
}

Example:

Item[] items = { new Item {Id = 1, Items = new List<Item> 
{ 
    new Item {Id = 2,  Items = new List<Item> {new Item { Id = 4, Items = new List<Item>()}}},
    new Item {Id = 3,  Items = new List<Item>()},
}}};

var path = Path(items, e => e.Items, e => e.Id == 4);

// prints '1 -> 2 -> 4'
Console.WriteLine(String.Join(" -> ", path.Select(i=>i.Id)));

Answer 2

I really don't know why you must have linq for this so I created a recursive alternative instead:

class Program
{
    static void Main(string[] args)
    {
        var item1 = new Item()
        {
            Id = 1,
            Items = new List<Item>()
            {
                new Item()
                {
                    Id = 2,
                    Items = new List<Item>()
                    {
                        new Item()
                        {
                            Id = 4,
                            Items = new List<Item>()
                        }
                    }
                },
                new Item()
                {
                    Id = 3,
                    Items = new List<Item>()
                }
            }
        };
        var path = GetPath(item1, (i) => i.Id == 3);
        foreach (var item in path)
        {
            Console.WriteLine(item.Id);
        }
        Console.ReadLine();
    }

    private static IEnumerable<Item> GetPath(Item item, Func<Item, bool> predicate)
    {
        return GetPathRecursive(item, predicate, new List<Item>());
    }

    private static IEnumerable<Item> GetPathRecursive(Item item, Func<Item, bool> predicate, IEnumerable<Item> items)
    {
        var resultCandidate = items.Concat(new List<Item> { item });
        if (predicate(item))
        {
            return resultCandidate;
        }
        else
        {
            if (item.Items == null || item.Items.Count == 0)
            {
                return new List<Item>();
            }
            foreach (var nextItem in item.Items)
            {
                var newResult = GetPathRecursive(nextItem, predicate, resultCandidate);
                if (newResult != null && newResult.Any())
                {
                    return newResult;
                }
            }
            return new List<Item>();
        }
    }
}

public class Item
{
    public int Id { get; set; }
    public IList<Item> Items { get; set; }
}

I tried it searching for both Item3 and Item4. You could probably improve the algorithm since I just threw it together in a couple of minutes.

Answer 3

And another solution based on your example

public static class StaticItem
{
    public static IEnumerable<T> Path<T>(
        this IEnumerable<T> source,
        Func<T, IEnumerable<T>> childrenSelector,
        Predicate<T> condition)
    {
        // no data, no processing
        if (source == null || !source.Any()) return null;

        // if condition matches, return list containing element
        var attempt = source.FirstOrDefault(t => condition(t));
        if (!Equals(attempt, default(T))) return new List<T> { attempt };

        // iterate current items (btw: already done by FirstOrDefault)
        foreach (var item in source)
        {
            // select children
            IEnumerable<T> childs = childrenSelector(item);

            var x = childs.Path(childrenSelector, condition);

            // if element was found in path, the result is not null
            if (x != null)
            {
                // adding item to list
                var list = new List<T>();
                list.Add(item);
                list.AddRange(x);
                return list;
            }
        }
        return null;
    }
}

    static void Main()
    {
        Item item1 = new Item { Id = 1 };
        Item item2 = new Item { Id = 2 };
        Item item3 = new Item { Id = 3 };
        Item item4 = new Item { Id = 4 };

        item1.Items = new List<Item> { item2, item3 };
        item2.Items = new List<Item> { item4 };

        List<Item> all = new List<Item> { item1 };

        var x = all.Path( item => item.Items, i => i.Id == 4);
    }