How to recurse over items having cyclic dependencies

Question

I'm looking for a better way of recursing over items that may have cyclic dependencies. Currently, I pass a list of already processed items along in order to not process them again, but that is probably not the best way to do it.

Here's what I'm currently doing:

---

        /// <summary>
    /// caching dependencies in order to increase performance
    /// </summary>
    private static readonly IDictionary<string, IEnumerable<OwnedItem>> dependencies
        = new Dictionary<string, IEnumerable<OwnedItem>>();

        /// <summary>
    /// recursively find OwnedItem this oi depends upon
    /// in order to correctly handle cyclic dependencies, already considered
    /// dependencies need to be supplied as well (can be null or empty)
    /// </summary>
    /// <param name="oi"></param>
    /// <param name="parentDeps"></param>
    /// <returns></returns>
    private static IEnumerable<OwnedItem> GetDependencies(
        OwnedItem oi,
        IEnumerable<OwnedItem> parentDeps)
    {
        if (null == oi)
        {
            return Enumerable.Empty<OwnedItem>();
        }
        if (dependencies.ContainsKey(oi.UniqueId))
        {
            return dependencies[oi.UniqueId];
        }
        var comparer = new TCObjectComparer<OwnedItem>();
        var result = new HashSet<OwnedItem>(comparer);
        result.Add(oi);
        result.UnionWith(parentDeps ?? Enumerable.Empty<OwnedItem>());
        foreach (var oi2 in oi.AllUsedOwnedItemsToBeIncluded.Except(
                result, comparer))
        {
            result.UnionWith(GetDependencies(oi2, result));
        }
        dependencies[oi.UniqueId] = result;
        return result;
    }

---

The items are of type 'OwnedItem' and keep a list (IEnumerable<OwnedItem>) of their direct dependencies in property AllUsedOwnedItemsToBeIncluded but basically this should apply whenever 'items' keep a list of 'items' where cyclic dependencies can occur. Using the dictionary just avoids doing the same calculation more than once; it is not essential. Also, only a single instance of TCObjectComparer is needed, but that is not essential, either. Any suggestions? I think there must exist some classic algorithm to handle this, but I can't find it.

Answer 1

What you are trying to do is basically going through all the nodes of a connected graph. Your AllUsedOwnedItemsToBeIncluded property is the list of nodes connected to your current node.

You can have a look here to find some graph traversal algorithms that might help.

You algorithm is one way of doing a graph traversal. You'll have to go through each node and keep a list of the visited nodes to not visit him twice.

One other algorithm which reduces the number of traversals can be:

list nodesToExplore;
list exploredNodes;
nodesToExplore.add(startNode);

for all node in nodesToExplore
{
    nodesToExplore.remove(node);
    exploredNodes.add(node);

    for all child in node.childs
    {
        if(child not in exploredNodes)
           nodesToExplore.add(child);
    }
}

When it ends, the exploredNodes will contain what you need. Using an hashset/dictionnary instead of a list will improve the performance