1

I have the following hierarchy and I need to flatten this and select all Ids. I have tried using SelectMany() like this .SelectMany(node => node.Children).Select(node => node.Id). This will result in a list of 3,5,6. Is it possible, using Linq to get the complete list 1,2,3,4,5,6,7?

  • Node (Id = 1)
  • Node (Id = 2)
    • Node (Id = 3)
  • Node (Id = 4)
    • Node (Id = 5)
    • Node (Id = 6)
      • Node (Id = 7)
marcus
  • 9,616
  • 9
  • 58
  • 108

3 Answers3

2

You can use following extension method for flattening hierarchy (see alternative flattening algorithm in answer update below):

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector)
{
    foreach (var item in source)
    {
        yield return item;

        var children = childrenSelector(item);
        if (children == null)
            continue;

        foreach (var child in children.Flatten(childrenSelector))
            yield return child;                
    }
}

I takes child selector and recursively yields children. Then projection is simple:

var result = nodes.Flatten(n => n.Children).Select(n => n.Id);

Assume you have following Node class:

public class Node
{    
    public Node(int id, params Node[] children)
    {
        Id = id;
        if (children.Any())
            Children = new List<Node>(children);
    }

    public int Id { get; set; }
    public List<Node> Children { get; set; }
}

Then with your sample hierarchy:

List<Node> nodes = new List<Node> {
    new Node(1),
    new Node(2, new Node(3)),
    new Node(4, new Node(5),
                new Node(6, new Node(7)))
};

Output will be:

1, 2, 3, 4, 5, 6, 7

UPDATE: You can flatten hierarchy without usage of recursion (for better performance):

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector)
{
    Queue<T> queue = new Queue<T>();
    foreach (var item in source)
        queue.Enqueue(item);

    while (queue.Any())
    {
        T item = queue.Dequeue();
        yield return item;
        var children = childrenSelector(item);
        if (children == null)
            continue;

        foreach (var child in children)
           queue.Enqueue(child);
    }
}
Sergey Berezovskiy
  • 232,247
  • 41
  • 429
  • 459
  • I think your non-recursive version does a breadth first traversal, which may or may not matter but which should probably be noted. (It will result in 1,2,4,3,5,6,7) – Steve Ruble Jan 18 '14 at 14:53
  • @SteveRuble Changing it to depth first is as trivial as changing the `Queue` to a `Stack`. Changing it to a best-first traversal is as trivial as changing it to a Priority Queue. – Servy Jan 18 '14 at 15:06
0

Easy.

Func<IEnumerable<Node>, IEnumerable<int>> flatten = null;
flatten = ns =>
{
    return ns.Select(n => n.Id)
        .Concat(ns.SelectMany(n => flatten(n.Children)));
};
Enigmativity
  • 113,464
  • 11
  • 89
  • 172
0

You can flatten the hierarchy with an extension method:

public static IEnumerable<Node> Flatten(this IEnumerable<Node> source)
{
  if(source == null) 
    throw new ArgumentNullException("source");

  return FlattenIterator(source);
}

private static IEnumerable<Node> FlattenIterator(IEnumerable<Node> source)
{
  foreach(var node in source)
  {
    yield return node;
    foreach(var child in node.Children.Flatten())
    {
      yield return child;
    }
  }
}

Then you can select the IDs like this:

var ids = source.Flatten().Select(n => n.Id);
Steve Ruble
  • 3,875
  • 21
  • 27