Skip to content

Instantly share code, notes, and snippets.

@ericoporto
Created February 2, 2020 07:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ericoporto/17cf45a3112098cedb150d13828f9415 to your computer and use it in GitHub Desktop.
Save ericoporto/17cf45a3112098cedb150d13828f9415 to your computer and use it in GitHub Desktop.
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" );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment