Reading the last child item in a hierarchy using Linq

Question

I have a table that holds a hierarchy as below

ParentChildMap
{
    parent_id,
    child_id
}

Another table holds the details of each member in the Map

Member_Details
{
    Member_Id,
    Member_Name
}

Sometimes the relation can be as simple as Parent--->Child or sometimes the relation can have multiple levels such as GG-GrandFather--> G-GrandFather---> GrandFather ---> Parent --->Child.

What I want to do is to list all Children of a given family with their details.

Can somebody help me with the most efficient LINQ query for this?

I think you'll need some recursion for that, but beware of circular graphs. — Stefan, Oct 08 '14 at 12:32
Does it really have to be LINQ, recursion is a sure way to do this. — Thulani Chivandikwa, Oct 08 '14 at 12:35
I Agree with @Stefan, you need recursion. See [link]http://stackoverflow.com/questions/4814242/linq-recursion-function for related issue. — Emil G, Oct 08 '14 at 12:36
For now we can assume that maximum of 5 Levels need to be traversed. — user3206213, Oct 08 '14 at 13:06

score 0 · Answer 1 · answered May 07 '19 at 15:22

I realize this question has been unanswered for more than 4 years, but it seemed like a fun question. I think the following approach should work with a Linq query. I'm basically postulating that children are not parents. So if this is true, then a relationship left-join on itself should produce all nodes that are not parents. Once this is done a regular join to the details will match the name of the child node. Following is my example code:

void Main()
{
    //    1
    //   2 3
    //  4    
    // 5 6

    // Child nodes are all those that are not parents: i.e.: 5, 6, 3

    var details = new[] {
        new Member_Details { Member_Id = 1, Member_Name = "Node 1" },
        new Member_Details { Member_Id = 2, Member_Name = "Node 2" },
        new Member_Details { Member_Id = 3, Member_Name = "Node 3" },
        new Member_Details { Member_Id = 4, Member_Name = "Node 4" },
        new Member_Details { Member_Id = 5, Member_Name = "Node 5" },
        new Member_Details { Member_Id = 6, Member_Name = "Node 6" },
    };

    var relationships = new[] {
        new ParentChildMap { parent_id = 1, child_id = 2 },
        new ParentChildMap { parent_id = 1, child_id = 3 },
        new ParentChildMap { parent_id = 2, child_id = 4 },
        new ParentChildMap { parent_id = 4, child_id = 5 },
        new ParentChildMap { parent_id = 4, child_id = 6 }
    };

    var children = relationships
        .GroupJoin(relationships, r1 => r1.child_id, r2 => r2.parent_id, (r1, r2) => r2
            .Select(x => new { Inner = r1.child_id, Outer = x.child_id})
            .DefaultIfEmpty(new { Inner = r1.child_id, Outer = 0 }))
        .SelectMany(x => x)
        .Where(x => x.Outer == 0)
        .Join(details, r => r.Inner, d => d.Member_Id, (r, d) => new {Id = r.Inner, Name = d.Member_Name});

    foreach (var child in children)
    {
        Console.WriteLine($"ID: {child.Id}, Name: {child.Name}");
    }
}

public class ParentChildMap
{
    public int parent_id;
    public int child_id;
}

public class Member_Details
{
    public int Member_Id;
    public string Member_Name;
}

Reading the last child item in a hierarchy using Linq

1 Answers1