How to Flatten Tree Via Linq

How to flatten tree via LINQ?

You can flatten a tree like this:

IEnumerable<MyNode> Flatten(IEnumerable<MyNode> e) =>
    e.SelectMany(c => Flatten(c.Elements)).Concat(new[] { e });

You can then filter by group using Where(...).

To earn some "points for style", convert Flatten to an extension function in a static class.

public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) =>
    e.SelectMany(c => c.Elements.Flatten()).Concat(e);

To earn more points for "even better style", convert Flatten to a generic extension method that takes a tree and a function that produces descendants from a node:

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> e
,   Func<T,IEnumerable<T>> f
) => e.SelectMany(c => f(c).Flatten(f)).Concat(e);

Call this function like this:

IEnumerable<MyNode> tree = ....
var res = tree.Flatten(node => node.Elements);

If you would prefer flattening in pre-order rather than in post-order, switch around the sides of the Concat(...).

Use LINQ to flatten tree getting deepest value

Linq operates on IEnumerables, so the first step would be to create one. For example by using an iterator block. You can then use .First() or any other linq methods to return the first non-null manager, or any other query you want.

    public Dictionary<Guid, TestDepartmemnt> departments = new Dictionary<Guid, TestDepartmemnt>();

    public IEnumerable<TestDepartmemnt> GetParents(Guid departmentId)
    {
        while(departments.TryGetValue(departmentId, out var department))
        {
            yield return department;
            departmentId = department.ParentTestDepartmentID;
        }
    } 

This assumes you have the departments in a dictionary. This can be replaced with whatever method you use to link ids to departments.

Flattening a tree of classes using SelectMany()

public class ObjectRelation
{
    public ObjectRelation(GetObjectParentChildList_Result relation)
    {
        this.ObjectId = relation.Object_ID;
        this.Parent = relation.Parent_Object;
        this.ChildObjects = new List<ObjectRelation>();
    }

    public int ObjectId { get; set; }
    public ObjectRelation Parent { get; set; }
    public List<ObjectRelation> ChildObjects { get; set; }
}

public static class ObjectRelationExtensions
{
  public static IEnumerable<ObjectRelation> Parents(this ObjectRelation obj)
  {
    while(obj.Parent!=null)
    {
      obj = obj.Parent;
      yield return obj;
    }
  }
}

Then to check:

if (x.Parents.Any(p=>p==x)) throw Exception();

or

if (x.Parents.Any(p=>p.ObjectId==x.ObjectId)) throw Exception();

How to flatten tree

Perfect use case for a recursive method

public static void DisplayPerson(List<Person> persons, int level = 0)
{
    if (persons != null)
    {
        level++;
        foreach (Person item in persons)
        {
            Console.WriteLine("-" + item.Name + ", Level" + level); 
            DisplayPerson(item.Childs, level);
        }
    }
}

https://dotnetfiddle.net/2J9F5K

Flattening a list of lists, using LINQ, to get a list of parent/child

Thanks to the comments on my initial post, I was able to get what I was looking for.

The solution only works on one level, which is what I needed. It could be made recursive to go deeper though:

var result = parents.SelectMany(person => person.Children
        .Prepend(person))
    .Select(p => p.Name);

Gave me the expected result:

parentA 
childB 
childC 
parentD 
childE 
childF 

Which then allowed me to use all the objects in the flattened lists, including the parent objects.

Recursive List Flattening

Hmm... I'm not sure exactly what you want here, but here's a "one level" option:

public static IEnumerable<TElement> Flatten<TElement,TSequence> (this IEnumerable<TSequence> sequences)
    where TSequence : IEnumerable<TElement> 
{
    foreach (TSequence sequence in sequences)
    {
        foreach(TElement element in sequence)
        {
            yield return element;
        }
    }
}

If that's not what you want, could you provide the signature of what you do want? If you don't need a generic form, and you just want to do the kind of thing that LINQ to XML constructors do, that's reasonably simple - although the recursive use of iterator blocks is relatively inefficient. Something like:

static IEnumerable Flatten(params object[] objects)
{
    // Can't easily get varargs behaviour with IEnumerable
    return Flatten((IEnumerable) objects);
}

static IEnumerable Flatten(IEnumerable enumerable)
{
    foreach (object element in enumerable)
    {
        IEnumerable candidate = element as IEnumerable;
        if (candidate != null)
        {
            foreach (object nested in candidate)
            {
                yield return nested;
            }
        }
        else
        {
            yield return element;
        }
    }
}

Note that that will treat a string as a sequence of chars, however - you may want to special-case strings to be individual elements instead of flattening them, depending on your use case.

Does that help?

---

Related Topics