Сглаженная коллекция иерархии объектов в глубину с использованием LINQ

У меня есть иерархия объектов (MasterNode -> ChildNodes), где главный и дочерний узлы имеют один и тот же тип, и есть только два уровня (верхний уровень и дочерние элементы), подобных этому ('A' является родительским для D, E и F, ' B 'является родительским для G и т. Д.)

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

Предположим, у меня есть MasterNodes в качестве IEnumerable родительских объектов (A, B, C), и, учитывая родительский объект X, я могу получить IEnumerable его дочерних объектов с помощью X. дети

Я знаю, что могу перечислить все листы (дочерние узлы) с помощью метода SelectMany или с помощью

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

Это даст мне такую ​​последовательность:

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

, но я не об этом прошу.

Что такое запрос LINQ для получения последовательности объектов в коллекции MasterNodes в первую очередь в глубину? (вернуть первого родителя, затем всех его дочерних узлов, затем следующего родителя, затем всех его дочерних узлов и т. д.)

Ожидаемый результат должен быть такой:

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

ОБНОВЛЕНИЕ:

Я прошу чистый LINQ, готовый к .NET. Я знаю, что могу определять свои собственные методы, но мне нужно что-то, основанное только на методах, предоставляемых фреймворком.


c# flatten linq hierarchy depth-first-search
person Thanasis Ioannidis    schedule 03.09.2012    source источник
comment
LINQ может помочь написать понятный код, но он не содержит метода EnumerateDepthFirstTwoLevelDeep. Вам нужно составить несколько методов LINQ, чтобы получить желаемый результат. Если бы такой метод существовал, на его поиск потребовалось бы больше времени, чем для написания нескольких строк сразу, потому что разработчикам LINQ потребовалось бы предоставить многие сотни, если не тысячи дополнительных методов, соответствующих вашему конкретному случаю, а также множеству различных.   -  person Alois Kraus    schedule 03.09.2012
comment
Это то, о чем я просил. Эти две строчки для этого конкретного случая :) Ответ Хейнци - именно то, что я хотел   -  person Thanasis Ioannidis    schedule 03.09.2012

Ответы (4)


arrow_upward
3
arrow_downward

Если вам нужно более двух уровней иерархии, вы можете использовать следующий метод расширения, который рекурсивно проходит через граф вашего объекта:

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

Он выравнивает заданный IEnumerable<T> с помощью функции, которая отображает T на IEnumerable<T>, описывающее отношение родительский -> дочерний в ваших данных.

Сглаживание по глубине выполняется путем объединения каждого элемента с его поддеревом и последующего соединения их с помощью SelectMany.

Вы можете использовать это так:

var flattened = Masternodes.Flat(c => c.children);
person Raziel    schedule 01.03.2018
comment
Ι Мне нравится этот ответ, потому что он более общий. - person Thanasis Ioannidis; 07.03.2018
comment
Пожалуйста, подумайте об изменении принятого ответа на этот ответ, если вы считаете, что это лучше. Спасибо! - person Raziel; 12.03.2018

arrow_upward
4
arrow_downward

Если у вас есть класс, как показано ниже

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

ваш linq будет

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

Код теста:

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);
person L.B    schedule 03.09.2012
comment
@DanielHilgarth Я знаю, что рекурсивная лямба не очень читабельна, но в итоге это 2 строки кода. - person L.B; 03.09.2012
comment
Вы также можете использовать стороннюю библиотеку графов, такую ​​как nuget.org/packages/QuickGraph, которая включает рекурсию с глубиной . - person akton; 03.09.2012
comment
@ L.B: Лично я бы сделал это обычным рекурсивным методом, так как он более читабельный. - person Daniel Hilgarth; 03.09.2012

arrow_upward
2
arrow_downward

Поскольку у вас всего два уровня, следующий подход должен работать:

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

Во-первых, он создает перечислимые элементы родительского элемента и его дочерних элементов:

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

а затем сглаживает их с помощью SelectMany.

person Heinzi    schedule 03.09.2012
comment
Спасибо, это именно то, что мне пришло в голову вскоре после того, как я разместил вопрос. Есть ли метод LINQ для преобразования объекта x в IEnumerable, который содержит этот объект? Или мне нужно использовать новый способ Node [] {...}? - person Thanasis Ioannidis; 03.09.2012
comment
Хотя это не единственный ответ на вопрос, я выбрал его, потому что он короткий, быстрый, чистый и подходящий - person Thanasis Ioannidis; 03.09.2012
comment
@Saysmaster: Нет ничего действительно элегантного для создания одноэлементного IEnumerable. Другой вариант - Enumerable.Repat(item, 1) (см. this вопрос) или создание для этой цели метода расширения (см. этот вопрос ). - person Heinzi; 03.09.2012

arrow_upward
0
arrow_downward

Скажем, у нас есть следующие классы:

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

public class ChildNode
{
    public string Value;
}

тогда

        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);
        }
person horgh    schedule 03.09.2012