locked
LINQ and recursive functions

    Question

  • Hello all,

    I'm blocked with a LINQ query
    I have the following class :

          public class MyClass
          {
             public MyClass(int val)
             {
                this.Val = val;
             }

             public int Val;
             public List<MyClass> MyList = new List<MyClass>();
          }

          static void Main(string[] args)
          {
             MyClass c1 = new MyClass(10);
             MyClass c2 = new MyClass(20);
             c1.MyList.Add(c2);
             c2.MyList.Add(c1);
          }


    I want to be able to extract the sum of the "Val" property of c1 : ie c1.Val + the value of all classes in MyList.
    In this case, it's simple, I juste do
     return c1.Val
                   + c1.MyList.Sum(c => c.Val);

    Now let's add recursion :

          static void Main(string[] args)
          {
             MyClass c1 = new MyClass(10);
             MyClass c2 = new MyClass(20);
             MyClass c3 = new MyClass(20);
             c1.MyList.Add(c2);
             c2.MyList.Add(c1);
             c2.MyList.Add(c3);
             c3.MyList.Add(c2);
          }

    (Of course, c3 can also be linked with other classes, ...)
    Here I'm a bit stuck. Which kind of query can I write to extract c1.Val + the value of all in c1.MyList + the value of all in c.MyList where c is in c1.MyList + ...

    This is typically the kind of query I would write with a "WITH ... UNION ..." query in SQL but I haven't found an "equivalent" in LINQ

     

    Any idea ?

    I have seen that there was the YCombinator extension method but I'm not sure to understand correctly how it works.

     


    Many thanks,

    Monday, June 04, 2007 8:56 AM

Answers

  • There has not been a recursive query operator defined yet for LINQ.  Of course, you've defined a cyclic data structure, so even if there were a recursive operator it would likely fail.

     

    Here is a recursive traversal operator you could use.  It may have some typos.  It converts your deep hierarchy into a flat sequence.

     

    public static class MyExtensions {

       public static IEnumerable<T> Traverse(this IEnumerable<T> source, Func<T, IEnumerable<T>> fnRecurse) {

               foreach(T item in source) {

                      yield return item;

                      IEnumerable<T> seqRecurse = fnRecurse(item);

                      if (seqRecurse != null) {

                          foreach(T itemRecurse in Traverse(seqRecurse, fnRecurse)) {

                             yield return itemRecurse;

                          }

                      }

               }

    }

     

    To traverse all values in your collection:

     

    List<MyClass> list = ...;

     

    var total = list.Traverse(x => x.MyList).Sum(x => x.Val).

     

     

    Tuesday, June 05, 2007 4:20 AM

All replies

  • Hi,

    you can use the Union standard operator:

     

    Code Snippet
    var productFirstChars =
            from p in products
            select p.ProductName[0];
      var customerFirstChars =
            from c in customers
            select c.CompanyName[0];
        
      var uniqueFirstChars = productFirstChars.Union(customerFirstChars);

     

    I've taken this sample from here where you can see much other samples you could be find useful.

    Best,

    Fabio

     

     

    Monday, June 04, 2007 10:21 AM
  • There has not been a recursive query operator defined yet for LINQ.  Of course, you've defined a cyclic data structure, so even if there were a recursive operator it would likely fail.

     

    Here is a recursive traversal operator you could use.  It may have some typos.  It converts your deep hierarchy into a flat sequence.

     

    public static class MyExtensions {

       public static IEnumerable<T> Traverse(this IEnumerable<T> source, Func<T, IEnumerable<T>> fnRecurse) {

               foreach(T item in source) {

                      yield return item;

                      IEnumerable<T> seqRecurse = fnRecurse(item);

                      if (seqRecurse != null) {

                          foreach(T itemRecurse in Traverse(seqRecurse, fnRecurse)) {

                             yield return itemRecurse;

                          }

                      }

               }

    }

     

    To traverse all values in your collection:

     

    List<MyClass> list = ...;

     

    var total = list.Traverse(x => x.MyList).Sum(x => x.Val).

     

     

    Tuesday, June 05, 2007 4:20 AM
  • I had to use Traverse<T> to get this to compile:

    public static IEnumerable<T> Traverse<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> fnRecurse)
    Wednesday, December 03, 2008 11:03 PM
  • Thanks for that pretty extension.
    Is it possible that, this extension dont destroy the data struct of the model?

    If i make something like that:

                var x = from c in MyClass.MyList.Traverse(c=>c.MyList)
    
                        where c.Val== 1
    
                        select c;
    
    

    The result would put in one list. So i got a List with all MyClass object which are equal to Val = 1. Thats good. But better would be if he dont destroy the model of the object.

    If i got this list

    List<MyClass>
    +MyClass
    ++Val = 1
    ++MyList
    ++-MyClass
    ++-Val =1
    ++-MyList ...

    and i use this Extension the result should look like above. I hope I described my problem well. If not please tell me.

    greetings
    http://get.lima-city.de
    Sunday, April 19, 2009 7:41 AM
  • Be careful, this code can cause stack overflow exceptions if you have cyclical references in your collections. Any ideas on how to update it to prevent that as an extension method?
    Tuesday, December 01, 2009 8:07 AM
  • It would have to track (with references, possibly WeakReferences) all previously-yielded objects and prevent itself from recursing into them. At that point, I'd be more afraid of memory use. And with that in mind, a simple yield won't be good enough and you're back in the realm of a full IEnumerator<T> implementation that doesn't return something that has already been returned.
    Tuesday, April 23, 2013 12:29 AM
  • I am unable to access this method.

    list.Traverse is not appearing.

    Am I missing something.

    Tuesday, September 10, 2013 10:16 AM