Jak wyszukiwać dane hierarchiczne za pomocą Linq

Question

Muszę przeszukać drzewo w poszukiwaniu danych, które mogą znajdować się w dowolnym miejscu w drzewie. Jak to zrobić z linq?

class Program 
{ 
    static void Main(string[] args) { 

     var familyRoot = new Family() {Name = "FamilyRoot"}; 

     var familyB = new Family() {Name = "FamilyB"}; 
     familyRoot.Children.Add(familyB); 

     var familyC = new Family() {Name = "FamilyC"}; 
     familyB.Children.Add(familyC); 

     var familyD = new Family() {Name = "FamilyD"}; 
     familyC.Children.Add(familyD); 

     //There can be from 1 to n levels of families. 
     //Search all children, grandchildren, great grandchildren etc, for "FamilyD" and return the object. 


    } 
} 

public class Family { 
    public string Name { get; set; } 
    List<Family> _children = new List<Family>(); 

    public List<Family> Children { 
     get { return _children; } 
    } 
} 

Answer 1

to rozszerzenie It'sNotALie.s answer.

public static class Linq 
{ 
    public static IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector) 
    { 
     return selector(source).SelectMany(c => Flatten(c, selector)) 
           .Concat(new[] { source }); 
    } 
} 

Próbka Wykorzystanie testu:

var result = familyRoot.Flatten(x => x.Children).FirstOrDefault(x => x.Name == "FamilyD"); 

Zwraca familyD obiektu.

Można zrobić to praca na IEnumerable<T> źródła TOO:

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector) 
{ 
    return source.SelectMany(x => Flatten(x, selector)) 
     .Concat(source); 
} 

Answer 2

Proste:

familyRoot.Flatten(f => f.Children); 
//you can do whatever you want with that sequence there. 
//for example you could use Where on it and find the specific families, etc. 

IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector) 
{ 
    return selector(source).SelectMany(c => Flatten(selector(c), selector)) 
          .Concat(new[]{source}); 
} 

Answer 3

Cóż, myślę sposobem jest pójść z techniką pracy z hierarchicznych struktur:

1. potrzebujesz kotwicę, aby

2. Potrzebujesz części rekurencyjnej

   // Anchor 
   
   rootFamily.Children.ForEach(childFamily => 
   { 
       if (childFamily.Name.Contains(search)) 
       { 
        // Your logic here 
        return; 
       } 
       SearchForChildren(childFamily); 
   }); 
   
   // Recursion 
   
   public void SearchForChildren(Family childFamily) 
   { 
       childFamily.Children.ForEach(_childFamily => 
       { 
        if (_childFamily.Name.Contains(search)) 
        { 
         // Your logic here 
         return; 
        } 
        SearchForChildren(_childFamily); 
       }); 
   } 
   

Answer 4

Zatem najprostszą opcją jest napisanie funkcji przechodzącej przez twoją hierarchię i tworzącej pojedynczą sekwencję. To następuje na początku operacji LINQ, np.

IEnumerable<T> Flatten<T>(this T source) 
    { 
     foreach(var item in source) { 
     yield item; 
     foreach(var child in Flatten(item.Children) 
      yield child; 
     } 
    } 

do połączenia wystarczy: familyRoot.Flatten(), gdzie (n => n.Name == "Bob").

Nieznaczne alternatywą byłoby dać drogę do szybkiego pominięcia całego oddziału:

IEnumerable<T> Flatten<T>(this T source, Func<T, bool> predicate) 
    { 
     foreach(var item in source) { 
     if (predicate(item)) {   
      yield item; 
      foreach(var child in Flatten(item.Children) 
       yield child; 
     } 
    } 

Następnie można zrobić rzeczy jak: family.Flatten (n => n.Children.Count> 2) .gdzie (...)

Answer 5

Innym rozwiązaniem bez rekursji ...

var result = FamilyToEnumerable(familyRoot) 
       .Where(f => f.Name == "FamilyD"); 


IEnumerable<Family> FamilyToEnumerable(Family f) 
{ 
    Stack<Family> stack = new Stack<Family>(); 
    stack.Push(f); 
    while (stack.Count > 0) 
    { 
     var family = stack.Pop(); 
     yield return family; 
     foreach (var child in family.Children) 
      stack.Push(child); 
    } 
} 

Answer 6

próbowałem dwa z proponowanych kodów i złożony kod nieco bardziej jasne:

public static IEnumerable<T> Flatten1<T>(this T source, Func<T, IEnumerable<T>> selector) 
    { 
     return selector(source).SelectMany(c => Flatten1(c, selector)).Concat(new[] { source }); 
    } 

    public static IEnumerable<T> Flatten2<T>(this T source, Func<T, IEnumerable<T>> selector) 
    {    
     var stack = new Stack<T>(); 
     stack.Push(source); 
     while (stack.Count > 0) 
     { 
      var current = stack.Pop(); 
      yield return current; 
      foreach (var child in selector(current)) 
       stack.Push(child); 
     } 
    } 

Flatten2() wydaje się być trochę szybszy, ale jest bliski.

Answer 7

Podoba mi się odpowiedź Kennetha Bo Christensena za pomocą stosu, działa świetnie, jest łatwa do czytania i jest szybka (i nie używa rekursji). Jedyną nieprzyjemną rzeczą jest to, że odwraca kolejność elementów podrzędnych (ponieważ stos jest FIFO). Jeśli kolejność sortowania nie ma dla ciebie znaczenia, to jest w porządku. Jeśli tak, sortowanie można łatwo uzyskać za pomocą selektora (bieżącego). Odwróć() w pętli foreach (reszta kodu jest taka sama, jak w oryginalnym wpisie Kennetha) ...

Answer 8

Kilka innych wariantów odpowiedzi na pytania: It'sNotalie., MarcinJuraszek i DamienG.

Po pierwsze, dwa poprzednie dają sprzeczne z intuicją polecenie. Aby uzyskać ładne uporządkowanie drzewa do wyników, po prostu odwróć konkatenację (najpierw umieść "źródło").

Po drugie, jeśli pracujesz z drogim źródłem, takim jak EF, i chcesz ograniczyć całe gałęzie, sugestia Damiena, że ​​wstrzykniesz predykat jest dobra i nadal można zrobić z Linq.

Na koniec, w przypadku kosztownego źródła, dobrze jest wstępnie wybrać pola zainteresowań z każdego węzła za pomocą selektora z wtryskiem.

Umieszczenie tych wszystkich razem:

public static IEnumerable<R> Flatten<T,R>(this T source, Func<T, IEnumerable<T>> children 
    , Func<T, R> selector 
    , Func<T, bool> branchpredicate = null 
) { 
    if (children == null) throw new ArgumentNullException("children"); 
    if (selector == null) throw new ArgumentNullException("selector"); 
    var pred = branchpredicate ?? (src => true); 
    if (children(source) == null) return new[] { selector(source) }; 

    return new[] { selector(source) } 
     .Concat(children(source) 
     .Where(pred) 
     .SelectMany(c => Flatten(c, children, selector, pred))); 
}