How to build path to root element by knowing child parentId in LINQ?

Question

I have List< MyClass > like

ID  ParentID
1   0
2   7
3   1
4   5
5   1
6   2
7   1
8   6
9   0
10  9

And I need to get full path to root like

0 __ 1__ 7__ 2__ 6__ 8

if we know 8 6

I mean I need to go from parent to root element and build the hierarhy.

(I have tried this LINQ to SQL - Grouping categories by parentId so far.)

What is the simplest way to achieve this in linq?

i have a feeling this is going to need some form of recursion rather than linq — jazb, Nov 01 '18 at 03:12
I assume that in theory, and this might be wrong as it is late, you could put in a loop and keep just querying against the parent id until you get an object that has parentid in its result set — SomeStudent, Nov 01 '18 at 04:22
@SomeStudent - https://stackoverflow.com/questions/410026/proper-use-of-yield-return — jazb, Nov 01 '18 at 04:42

score 3 · Accepted Answer · answered Nov 01 '18 at 04:24

This problem is not well suited to LINQ, although you could write an extension method to perform the search and return an IEnumerable<MyClass> that represents the route back to root. Given the possibility of infinite loops and routes that do not complete, it's probably a good idea to track progress through the graph ensuring that a specific Id is not visited more than once.

public static class MyClassEx
{
    public static IEnumerable<MyClass> FindSourcePath(
        this MyClass startItem, 
        IList<MyClass> items)
    { 
        return startItem.FindSourcePath(items.ToDictionary(x => x.Id));
    }
    public static IEnumerable<MyClass> FindSourcePath(
        this MyClass startItem, 
        IDictionary<int, MyClass> itemDic)
    {
        var curr = startItem;
        var visited = new HashSet<int>();
        while (visited.Add(curr.Id))
        {
            yield return curr;
            if (curr.ParentId == 0)
            {
                yield break;
            }
            if (!itemDic.TryGetValue(curr.ParentId, out curr))
            {
                throw new Exception("invalid parent ref");
            }
        }
        throw new Exception("loop detected");
    }
}

And use it:

List<MyClass> allItems = //...
var someItem = allItems[7];
IEnumerable<MyClass> hopsToRoot = someItem.FindSourcePath(allItems);

to yield (in your example) the sequence

-------------
| MyClass   |
-------------
Id | ParentId
=============
8  | 6 
6  | 2 
2  | 7 
7  | 1 
1  | 0

+1 for using yield, learned something new while browsing through SO. So if I understood the docs, the yield will add the current element to the hash set, and then on next loop iteration it should start on the if statement? Or does the yield keyword allow continued execution of the loop even after it hit that return? — SomeStudent, Nov 01 '18 at 04:38
@SomeStudent It would be very difficult to clear up some of your details of your question in the context of the comments. I suggest a read up ([this](https://www.kenneth-truyers.net/2016/05/12/yield-return-in-c/) article seems to present in quite a straightforward way) and to ask a question if you come unstuck. The magic of `IEnumerable/IEnumerator` and the `yield` statement can't be covered here (but is well worth looking into). — spender, Nov 01 '18 at 04:53

How to build path to root element by knowing child parentId in LINQ?

1 Answers1