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