Quelle est la meilleure façon de trouver tous les enfants à charge dans une collection IEnumerable

Question

j'ai une base de données avec 2 tables:

1. Articles
2. ItemDependencies

Articles a clé ID

ItemLes dépendances ont deux colonnes: ItemId et DependsOnItemId

Je Conver ce à une collection:

IEnumerable<Item> items = GetItems(); 

chaque article a un: dépendances propriété qui est un

List<Item> 

donc je veux filtrer les éléments initiaux liste à:

1. Étant donné un seul élément, je veux une liste de cet élément et de tous les éléments qui dépendent de cet élément récursivement. Étant donné un seul élément, je veux une liste de cet élément et de tous les autres éléments dont il dépend (également récursivement).

quelle est la meilleure façon de le faire en C#, LINQ, ou toute autre chose qui ferait l'affaire.

Answer 1

Pour obtenir une liste de toutes les dépendances d'un élément que vous pouvez utiliser la fonction récursive suivante:

IEnumerable<Item> GetAllDependencies(Item i) 
{ 
    IEnumerable<Item> a = new Item[] { i }; 
    IEnumerable<Item> b = i.Dependencies 
          .SelectMany(d => GetAllDependencies(d)) 
          .Distinct(); 
    return a.Concat(b); 
} 

Cette méthode suppose qu'il n'y a pas de cycles dans la chaîne de dépendance (s'il y a un cycle, il sera s'appelle récursivement jusqu'à ce qu'il lance un StackOverflowException).

Pour faire l'inverse, je suggère de construire une nouvelle structure de données pour contenir les dépendances inverses, puis réutiliser la même technique.

Answer 2

Voici une façon d'obtenir toutes les valeurs.

public IEnumerable<Item> GetAllDependencies(Item search) 
{ 
    return PrivateGetAllDependencies(search, new HashSet<Item>()); 
} 

private IEnumerable<Item> PrivateGetAllDependencies(Item search, HashSet<Item> visited) 
{ 
    if (!visited.Contains(search)) 
    { 
     visited.Add(search); 
     foreach (Item child in search.Dependencies) 
     { 
      PrivateGetAllDependencies(child, visited); 
     } 
    } 
    return visited; 
} 

Et voici une façon d'obtenir toutes les références.

public IEnumerable<Item> GetAllBackReferences(Item search) 
{ 
    return PrivateGetAllBackReferences(search, search, new HashSet<Item>(), new HashSet<Item>()); 
} 

private IEnumerable<Item> PrivateGetAllBackReferences(Item search, Item target, HashSet<Item> visited, HashSet<Item> matched) 
{ 
    if (!visited.Contains(search)) 
    { 
     visited.Add(search); 
     if (search == target) 
     { 
      matched.Add(search); 
     } 
     foreach (Item child in search.Dependencies) 
     { 
      PrivateGetAllBackReferences(child, target, visited, matched); 
      if (child == target) 
      { 
       if (!matched.Contains(search)) 
       { 
        matched.Add(search); 
       } 
      } 
     } 
    } 
    return matched; 
} 

Les deux algorithmes doivent gérer les cycles dans le graphe de référence.