Recursive LINQ calls

Question

I'm trying to build an XML tree of some data with a parent child relationship, but in the same table.

The two fields of importance are

CompetitionID ParentCompetitionID

Some data might be

CompetitionID=1, ParentCompetitionID=null

CompetitionID=2, ParentCompetitionID=1

CompetitionID=3, ParentCompetitionID=1

The broken query I have simply displays results in a flat format. Seeing that I'm working with XML, some sort of recursive functionality is required. I can do this using normal for loop recursion, but would like to see the linq version. Any help appreciated.

var results = 
        from c1 in comps
        select new {
            c.CompetitionID,
            SubComps=
                from sc in comps.Where (c2 => c2.CompetitionID == c1.CompetitionID)
                select sc
        };

Update

I found an interesting article by Chris Eargle here that shows you how to call lambda delegates recursively. Here is the code. Thanks Chris!

Func<int, int> factoral = x => x <= 1 ? 1 : x + factoral(--x);

Func<int, int> factoral = null;

factoral = x => x <= 1 ? 1 : x + factoral(--x);

^ added code formatting to show the lamba funcs The trick is to assign null to the Func delegate first.

Answer 1

Don't know how to write a recursive LINQ. But I think no recursion is actually required here. A tree may be built in just two steps:

Dictionary<int, Competition> dic = comps.ToDictionary(e => e.CompetitionID);
foreach (var c in comps)
    if (dic.ContainsKey(c.ParentCompetitionID))
        dic[c.ParentCompetitionID].Children.Add(c);
var root = dic[1];

The root variable now contains the complete tree.

Here's a complete sample to test:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication2
{
    class Competition
    {
        public int CompetitionID;
        public int ParentCompetitionID;
        public List<Competition> Children=new List<Competition>();
        public Competition(int id, int parent_id) 
        { 
            CompetitionID = id; 
            ParentCompetitionID = parent_id; 
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            List<Competition> comps = new List<Competition>()
            {
                new Competition(1, 0), 
                new Competition(2,1),
                new Competition(3,1),
                new Competition(4,2),
                new Competition(5,3)
            };

            Dictionary<int, Competition> dic = comps.ToDictionary(e => e.CompetitionID);
            foreach (var c in comps)
                if (dic.ContainsKey(c.ParentCompetitionID))
                    dic[c.ParentCompetitionID].Children.Add(c);
            var root = dic[1];
        }
    }
}

Answer 2

I know I'm a little too late here. But you said you already had a version using foreach :) So if it should actually be recursive and use linq this would be a solution:

internal class Competition
{
    public int CompetitionID;
    public int ParentCompetitionID;

    public Competition(int id, int parentId)
    {
        CompetitionID = id;
        ParentCompetitionID = parentId;
    }
}

internal class Node
{
    public Node(int id, IEnumerable<Node> children)
    {
        Children = children;
        Id = id;
    }

    public IEnumerable<Node> Children { get; private set; }
    public int Id { get; private set; }
}

internal class Program
{
    static void Main(string[] args)
    {
        var comps = new List<Competition>
                        {
                            new Competition(1, 0),
                            new Competition(2, 1),
                            new Competition(3, 1),
                            new Competition(4, 2),
                            new Competition(5, 3)
                        };

        Node root = ToTree(0, comps);
    }

    static readonly Func<int, IEnumerable<Competition>, Node> ToTree = 
        (nodeId, competitions) => new Node(nodeId, from c in competitions where c.ParentCompetitionID == nodeId select ToTree(c.CompetitionID, competitions));
}