'Recursive' LINQ calls

Question

Hi,

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
        };

Answer 1

I've done something very similar using LINQ's group by

I don't use the query syntax of LINQ, so forgive me if this is wrong:

var results = from c in comps
    group c by c.ParentCompetitionID into g
    select new { ParentId = g.Key, ChildId = g };

Of course, this would be better if your classes looked something like:

class Competition {
   int Id;
   string Description;
   Competition ParentCompetition;
}

Then, instead of grouping by ID only, you can group by the entire competition, which makes generating the XML faster and easier.

var results = from c in comps
    group c by c.ParentCompetition into g
    select new { Parent = g.Key, Child = g };

Answer 2

class Competition
{ 
   int ID { get; set;}
   int ParentID { get; set; }
   IEnumerable<Competition> Children { get; set; } 
}

public IEnumerable<Competition> GetChildren(
   IEnumerable<Competition> competitions, int parentID)
{
   IEnumerable<Competition> children =
      competitions.Where(c => c.ParentID == parentID);

   if (children.Count() == 0)
      return null; 

   return children.Select(
      c => new Competition { ID = c.ID, Children = GetChildren(c.ID) };
}

Then you can just call GetChildren, passing the ID of the root as the parentID, and that will return a tree structure. You can also change the Competition object to the XML API of your choice.

I know this isn't exactly what you're looking for, but afaik LINQ doesn't support recursion. Nevertheless, the LIN part of LINQ means language integrated, which is exactly what I used.

Answer 3

While you can not do this with a single query (unless you are calling SQL directly with a CTE), you can limit the number of queries to the depth of the tree.

The code is too long to paste, but the basic steps are:

1. Collect root nodes and add to 'all' nodes
2. Collect nodes with parent in 'all' nodes (pass list to query)
3. Add nodes in step 2 to 'all' nodes
4. Repeat 2 - 3 till step 2 returns 0 nodes (which should be depth of tree + 1, I think).

You can minimize the amount of nodes passed to the query in step 2. SQL server tends to bomb out with a list of more than 2000 entries. (SQL Compact has no such issue though).

Answer 4

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 5

You can get a tree like structure, combining LINQ and recursion with delegates. In this example I use a XML structure like this:

<Competitions>
  <Competition ID="1" />
  <Competition ID="2" ParentCompetitionID="1" />
  <Competition ID="3" ParentCompetitionID="1" />
  <Competition ID="4" />
</Competitions>

So to store node data in code and facilitate navigation, create a class like this:

class Competition
{
   public int CompetitionID { get; set; }

   public IEnumerable<Competition> Childs { get; set; }
}

Now using Linq to XML you load the xml file into an XDocument. After that declare a delegate that iterates over all the xml elements inside the document selecting nodes that have an id mathing the delegate's id paremeter. When selecting each node, it calls to the delegate again, passing the id of the parent node to look for. It first starts with the id parameter set to null, so, selecting firts the root nodes:

    var doc = XDocument.Load("tree.xml");

    //Declare the delegate for using it recursively
    Func<int?, IEnumerable<Competition>> selectCompetitions = null;

    selectCompetitions = (int? id) =>
    {
       return doc.Elements("Competitions").Elements().Where(c => 
       {
         //If id is null return only root nodes (without ParentCompetitionID attribute)
         if (id == null)
            return c.Attribute("ParentCompetitionID") == null;
         else
            //If id has value, look for nodes with that parent id
            return  c.Attribute("ParentCompetitionID") != null &&
                    c.Attribute("ParentCompetitionID").Value == id.Value.ToString();
        }).Select(x => new Competition() 
                       { 
                      CompetitionID = Convert.ToInt32(x.Attribute("ID").Value),
                      //Always look for childs with this node id, call again to this
                      //delegate with the corresponding ID
                      Childs = selectCompetitions(Convert.ToInt32(x.Attribute("ID").Value))
                       });
};

var competitions = selectCompetitions(null);

To test it you can do a simply recurring method that prints the tree to the console:

private static void Write(IEnumerable<Competition> competitions, int indent)
{
   foreach (var c in competitions)
   {
       string line = String.Empty;

       for (int i = 0; i < indent; i++)
       {
          line += "\t";
       }

       line += "CompetitionID = " + c.CompetitionID.ToString();

       Console.WriteLine(line);

       if (c.Childs != null && c.Childs.Count() > 0)
       {
           int id = indent + 1;
           Write(c.Childs, id);
        }
   }
}

Hope it helps!

Answer 6

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));
}