C# – How to sort depended objects by dependency

algorithmcdependenciessortingtopological-sort

I have a collection:

List<VPair<Item, List<Item>> dependencyHierarchy;

The first item in pair is some object (item) and the second one is a collection of the same type objects that the first one depends on. I want to get a List<Item> in order of dependency, so there are not items that depend on the first element and so on (no cycled dependency!).

Input: 

Item4 depends on Item3 and Item5
Item3 depends on Item1
Item1 does not depend on any one
Item2 depends on Item4 
Item5 does not depend on any one

Result:

Item1
Item5
Item3
Item4
Item2

Thank you.

SOLUTION:

Topological Sorting (thanks to Loïc Février for idea)

and

example on C#, example on Java (thanks to xcud for great examples)

Best Answer

Having struggled with this for a while, here's my attempt at a Linq style TSort extension method:

public static IEnumerable<T> TSort<T>( this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle = false )
{
    var sorted = new List<T>();
    var visited = new HashSet<T>();

    foreach( var item in source )
        Visit( item, visited, sorted, dependencies, throwOnCycle );

    return sorted;
}

private static void Visit<T>( T item, HashSet<T> visited, List<T> sorted, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle )
{
    if( !visited.Contains( item ) )
    {
        visited.Add( item );

        foreach( var dep in dependencies( item ) )
            Visit( dep, visited, sorted, dependencies, throwOnCycle );

        sorted.Add( item );
    }
    else
    {
        if( throwOnCycle && !sorted.Contains( item ) )
            throw new Exception( "Cyclic dependency found" );
    }
}
Related Topic