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,

Answer 1

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

 

 

Answer 2

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).

 

 

Answer 3

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)

Answer 4

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

Answer 5

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?

Answer 6

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.