How do I return the ancestors of an object with LINQ?

Question

I have a District class that looks like this:

public class District
{
    public int Id { get; set; }
    public string Name { get; set; }
    public District Parent { get; set; }
    public IEnumerable<District> Ancestors { get { /* what goes here? */ } }
}

I would like to be able to get a list of each District's ancestors. So if District "1.1.1" is a child of District "1.1", which is a child of District "1", getting Ancestors on District "1.1.1" would return a list that contains the District objects whose names are "1.1" and "1".

Does this involve the yield return statement (I never totally understood that)? Can it be done in one line?

score 14 · Accepted Answer · answered May 13 '10 at 05:15

14

Everything can be done in one line, if the line is long enough :)

In this case, it's probably simplest done not in one line:

public IEnumerable<District> Ancestors
{
    get
    {
        District parent = Parent;
        while (parent != null)
        {
            yield return parent;
            parent = parent.Parent;
        }
    }
}

Just a brief plug if you want to understand yield return better - chapter 6 of the first edition of C# in Depth is still available for free, and that's all about iterators in C# 2. Grab it from the first edition page.

answered May 13 '10 at 05:15

Jon Skeet

1,421,763
867
9,128
9,194

what about a circular reference? – Elijah Glover May 13 '10 at 05:19
@Elijah: I'm assuming there *are* no circular references. If there are, you'd need to keep a set and do something like: while (parent != null && !visitedParents.Contains(parent)) – Jon Skeet May 13 '10 at 05:21
There are indeed no circular references, so this works perfectly. I ended up needing to include the current district in the list as well, but your code was very easy to read and modify. Thank you. I'll check out your book, too! – Christopher May 13 '10 at 05:31

score 2 · Answer 2 · edited May 23 '17 at 10:30

You may want to consider this alternative.... its not as "pure" but massively effective way to easily query for this kind of thing. (whether using sql or not)

SQL select descendants of a row

see the "Accepted" answer

the only thing I'd add is a delimiter between tags

oh and then to query using linq

ancestors = Districts.Where( d => 
       d.Pedigree.Contains(Id) && 
       d.Pedigree.Length < Pedigree)
       .ToList();

for the most if you are using an ORM this will result in a single query rather than many queries when trying to iterate the tree

actually in this case of a single parent, its even easier as your pedigree will contain your ancestry, but if you had a branching ancestry..... :)

score 1 · Answer 3 · answered Apr 12 '11 at 07:36

Here is a generic extension method for obtaining the collection of ancestors for an object, based on the accepted answer :

static public IEnumerable<T> GetAncestors<T>(this T source, Func<T, T> parentOf)
{
    var Parent = parentOf(source);
    while (Parent != null)
    {
        yield return Parent;
        Parent = parentOf(Parent);
    }
}

So I can use it for all hierarchies in my application :

public IEnumerable<District> Ancestors
{
    get
    {
        return this.GetAncestors(d => d.Parent);
    }
}

Or expand all parent nodes of a given TreeView node...

Node.GetAncestors(node => node.Parent).ToList().ForEach(n => n.Expanded = true);

It's really handy.

How do I return the ancestors of an object with LINQ?

3 Answers3

Linked