Depth-first flattened collection of an object hierarchy using LINQ

Question

I have an object hierarchy (MasterNode -> ChildNodes) where master and child nodes are of the same type, and there are only two levels (top level and children) like this ('A' is parent of D,E and F, 'B' is parent of G, etc)

A--+
|  D
|  E
|  F
|
B--+
|  G
|
C--+
   H
   I

Suppose I have a MasterNodes as an IEnumerable of the parent objects (A,B,C) and given a parent object X I can get an IEnumerable of its children by X.children

I know that I can enumerate all of the leaf (child nodes) with the SelectMany method or by using

from parent in Masternodes
from child in parent.children
select child

This will give me this sequence:

[D,E,F,G,H,I]

,but this is not what I am asking for.

What is the LINQ query to get a depth-first sequence of the objects in the MasterNodes collection? (return first parent then all of its children then next parent then all of its children etc etc)

The expected result should be a sequence like this:

[A,D,E,F,B,G,C,H,I]

UPDATE:

I am asking for pure .NET ready LINQ. I know that I can define my own methods to do things, but I want something that is based only on the framework provided methods.

LINQ can help to write understandable code but it does not contain a EnumerateDepthFirstTwoLevelDeep method. You need to compose several LINQ methods to get the desired result. If such a method would exist it would take longer to find it than to write the few lines at once because the LINQ designers would need to provide many hundreds if not thousands of additional methods to match your specific case and many different ones as well. — Alois Kraus, Sep 03 '12 at 08:30
That is what I was asking for. Those two lines for this specific case :) Heinzi's answer is exactly what I wanted — Thanasis Ioannidis, Sep 03 '12 at 12:12

score 4 · Answer 1 · answered Sep 03 '12 at 07:51

If you have a class like below

public class Node
{
    public string Name;
    public List<Node> Children = new List<Node>();
}

your linq would be

 Func<IEnumerable<Node>, IEnumerable<Node>> Flatten = null;
 Flatten = coll => coll.SelectMany(n=>n.Concat(Flatten(n.Children)));

Test Code:

Node[] roots = new Node[]{ new Node(){Name="A"},new Node(){Name="B"},new Node(){Name="C"} };
roots[0].Children.Add(new Node(){Name="D"});
roots[0].Children.Add(new Node(){Name="E"});
roots[0].Children.Add(new Node(){Name="F"});

roots[1].Children.Add(new Node(){Name="G"});

roots[2].Children.Add(new Node(){Name="H"});
roots[2].Children.Add(new Node(){Name="I"});

Func<IEnumerable<Node>, IEnumerable<Node>> Flatten = null;
Flatten = coll => coll.SelectMany(n=>n.Concat(Flatten(n.Children)));

var result = String.Join(",",Flatten(roots).Select(x=>x.Name));

Console.WriteLine(result);

@DanielHilgarth I know recursive lamba is not very readible but it is 2 lines of code in the end. — L.B, Sep 03 '12 at 07:54
You could also use a third party graph library like http://nuget.org/packages/QuickGraph which include depth first recursion. — akton, Sep 03 '12 at 07:58
@L.B: Personally, I would have made it a regular recursive method as it is more readable. — Daniel Hilgarth, Sep 03 '12 at 08:02

Raziel · Accepted Answer · 2018-03-01T11:54:12.997

3

If you need more than two hierarchy levels you can use the following extension method which goes recursively through your object graph:

public static IEnumerable<T> Flat<T>(this IEnumerable<T> l, Func<T, IEnumerable<T>> f) =>
        l.SelectMany(i => new T[] { i }.Concat(f(i).Flat(f)));

It flattens the given IEnumerable<T> with the use of a function that maps a T to an IEnumerable<T> describing the parent -> children relation of your data.

The depth-first flattening is done by concatinating every element with its sub-tree and then joining them with SelectMany.

You can use it like this:

var flattened = Masternodes.Flat(c => c.children);

edited Mar 01 '18 at 11:54

answered Mar 01 '18 at 09:09

Raziel

64
5

ΙI like this answer because it is more generic. – Thanasis Ioannidis Mar 07 '18 at 11:18
Please consider changing the accepted answer to this answer if you think it is better. Thank you! – Raziel Mar 12 '18 at 11:42

score 2 · Answer 3 · answered Sep 03 '12 at 07:55

2

Since you have only two levels, the following approach should work:

var result = (from parent in masternodes
              select new Node[] { parent }.Concat(parent.children)).SelectMany(i => i);

First, it creates enumerables of the parent plus its children:

[A, D, E, F]
[B, G]
[C, H]

and then it flattens them with SelectMany.

answered Sep 03 '12 at 07:55

Heinzi

167,459
57
363
519

Thanks, this is actually what came to my mind shortly after I posted the question. Is there a LINQ method to convert an Object x into an IEnumerable that contains this object? Or I have to use the new Node[]{...} way? – Thanasis Ioannidis Sep 03 '12 at 08:14
Although it's not the only reply that answers the question, I picked it because it is short, quick, clean and right into the spot – Thanasis Ioannidis Sep 03 '12 at 08:26
1

@Saysmaster: There's nothing *really* elegant for creating a single-item IEnumerable. Another option would be `Enumerable.Repat(item, 1)` (see [this question](http://stackoverflow.com/questions/1019737/favorite-way-to-create-an-new-ienumerablet-sequence-from-a-single-value)) or creating an extension method for this purpose (see [this question](http://stackoverflow.com/questions/1577822/passing-a-single-item-as-ienumerablet)). – Heinzi Sep 03 '12 at 08:35

score 0 · Answer 4 · answered Sep 03 '12 at 07:41

Say, we have the following classes:

public class MasterNode : ChildNode
{
    public List<ChildNode> ChildNodes;
}

public class ChildNode
{
    public string Value;
}

then

        List<MasterNode> list = new List<MasterNode>
        {
            new MasterNode
            {
                Value="A", 
                ChildNodes = new List<ChildNode>
                {
                    new ChildNode{Value = "D"},
                    new ChildNode{Value = "E"},
                    new ChildNode{Value = "F"}
                }
            },
            new MasterNode
            {
                Value="B", 
                ChildNodes = new List<ChildNode>
                {                        
                    new ChildNode{Value = "G"}
                }
            },
            new MasterNode
            {
                Value="C", 
                ChildNodes = new List<ChildNode>
                {
                    new ChildNode{Value = "H"},
                    new ChildNode{Value = "I"}
                }
            }
        };

        foreach (ChildNode c in list.SelectMany(l =>
                                {
                                   List<ChildNode> result = l.ChildNodes.ToList();
                                   result.Insert(0, l);
                                   return result;
                                }))
        {
            Console.WriteLine(c.Value);
        }

Depth-first flattened collection of an object hierarchy using LINQ

4 Answers4

Linked

Related