Каков наилучший способ найти всех зависимых детей в коллекции IEnumerable - PullRequest
Новая
       14

Каков наилучший способ найти всех зависимых детей в коллекции IEnumerable

3 голосов
/ 17 июля 2010

У меня есть база данных с 2 таблицами:

  1. Предметы
  2. ItemDependencies

У предметов есть ключ ID

ItemDependencies имеют два столбца: ItemId и DependsOnItemId

Я конвертирую это в коллекцию: 

 IEnumerable<Item> items = GetItems();

каждый элемент имеет: Зависимости свойство, которое является 

List<Item>

Итак, я хочу отфильтровать начальный список элементов в:

  1. Учитывая один элемент, я хочу получить список этого элемента и всех элементов, которые рекурсивно зависят от этого элемента.

  2. Учитывая один элемент, я хочу получить список этого элемента и всех других элементов, от которых он зависит (также рекурсивно).

каков наилучший способ сделать это в C #, LINQ, или что-нибудь еще, что могло бы помочь?

Ответы [ 2 ]

5 голосов
/ 17 июля 2010

Чтобы получить список всех зависимостей элемента, вы можете использовать следующую рекурсивную функцию: 

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

Этот метод предполагает, что в цепочке зависимостей нет циклов (если есть цикл, он будет вызывать себя рекурсивно, пока не выдаст StackOverflowException).

Чтобы сделать обратное, я бы предложил создать новую структуру данных для хранения обратных зависимостей, а затем повторно использовать ту же технику.

0 голосов
/ 18 июля 2010

Вот один из способов получить все зависимости. 

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

И вот один из способов получить все обратные ссылки. 

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

Оба алгоритма должны обрабатывать циклы в контрольном графе.

...