Linq Query Puzzle

Question

If I have an object with a parent child relationship with Id and ParentId representing the unique Id of the record and the Parent Id of the record.

I need a query that will query a list of objects and return the path to the root of the relationship for each item (i.e. Path = (AllTheParentNames)\ Name ).

Any help with this would be appreciated.

MyObject

int Id
int? ParentId
string Name
string Path

Answer 1

I believe this would give you the expected result

        Func<int?, string> GetParents = null;

        List<URClass> lstRoot = new List<URClass>();
        lstRoot.Add(new URClass() { Id = 1, Name = "a", ParentId = null, Path = "1" });
        lstRoot.Add(new URClass() { Id = 2, Name = "b", ParentId = 1, Path = "1" });
        lstRoot.Add(new URClass() { Id = 3, Name = "c", ParentId = 2, Path = "1" });
        lstRoot.Add(new URClass() { Id = 4, Name = "d", ParentId = 3, Path = "1" });
        lstRoot.Add(new URClass() { Id = 5, Name = "e", ParentId = 4, Path = "1" });

        GetParents = i =>
        {
            var str = string.Empty;
            var outt = lstRoot.Where(x => x.Id == i).Select(x=>new {x.Name,x.ParentId });

            foreach (var lst in outt)
            {
                str += lst.Name;
                if (lst.ParentId != null)
                {
                      var outts = GetParents(lst.ParentId);
                      str += "," + outts;
                }                    
            }
            return str;

        };          

        var ks = from p in lstRoot
                 join q in lstRoot on p.Id equals q.ParentId
                 select new { q.Id, parentName = p.Name, parentid=p.Id, gpid=p.ParentId };


        List<string> RelationShip = new List<string>();

        foreach (var lst in ks)
        {
            var str = lst.parentName;
            if (lst.gpid != null)
            {
                 var prnt = GetParents(lst.gpid);
                 if (prnt != null)
                    str += "," + prnt;                   
            }
            str += "/" + lst.Id;
            RelationShip.Add(str); 
        }


        foreach (var ret in RelationShip)
            Console.WriteLine(ret);

the output will be

a/2

b,a/3

c,b,a/4

d,c,b,a/5

Answer 2

Is this the expected result?

class A
{
    public int Id;
    public int? ParentId;
    public string Name;


    public static Func<T1, T2> Fix<T1, T2>(Func<Func<T1, T2>, Func<T1, T2>> f)
    {
        return f(x => Fix(f)(x));
    }

    public static string[] GetPaths(A[] array)
    {
        return array.Select(
            Fix<A, string>(self => x => x.ParentId != null ? self(array.First(a => a.Id == x.ParentId.Value)) + "\\" + x.Name : x.Name)
            ).ToArray();
    }
}

it's impossible to make in single query without recursion (foreach (Aggregate) on array may be good for simulate recursion, but it's stupid)

Fix - is the Fixed point combinator

Answer 3

First, suppose you have a single node. You wish to get the path to the root.

Let's represent a path to a root as a sequence of nodes.

We can build this write a method that takes an item and a function that identifies the next item, and returns the sequence.

public static IEnumerable<T> Path(T item, Func<T, T> nextItem) where T : class
{
    T current = item;
    while(current != null)
    {
        yield return current;
        current = nextItem(current);
    }
}

Now you can write queries on your list of objects.

List<Node> nodes = whatever;
var paths = from node in nodes 
            select Path(node, n=>GetNodeById(n.Parent));

And now you have a sequence of sequences of nodes.

Suppose instead you want a sequence of sequences of strings:

var namePaths = 
    from node in nodes 
    select (from pathElement in Path(node, n=>GetNodeById(n.Parent)) 
            select pathElement.Name);

And so on.

Make sense?