What is the best way to find all dependent children in a IEnumerable collection

Question

I have a database with 2 tables:

1. Items
2. ItemDependencies

Items has key of ID

ItemDependencies have two columns: ItemId, and DependsOnItemId

I conver this to a collection:

 IEnumerable<Item> items = GetItems();

each item has a: Dependencies property which is a

List<Item>

So i want to filter the initial items list to:

1. Given a single item, i want a list of that item and all of the items that dependon this item recursively.

2. Given a single item, i want a list of that item and all of the other items that it depends on (also recursively).

what is the best way of doing this in C#, LINQ, or anything else that would do the trick.

Answer 1

To get a list of all the dependencies of an element you can use the following recursive function:

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

This method assumes that there are no cycles in the dependency chain (if there is a cycle it will call itself recursively until it throws a StackOverflowException).

To do the reverse I'd suggest building a new data structure to hold the reverse-dependencies and then reuse the same technique.

Answer 2

Here is one way of getting all depedencies.

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

And here is one way of getting all back references.

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

Both algorithms should handle cycles in the reference graph.