Skip to content

Instantly share code, notes, and snippets.

@jasondown
Created August 3, 2021 14:29
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 jasondown/8c012f8bf7061dbcaeaf61e3b6dd563d to your computer and use it in GitHub Desktop.
Save jasondown/8c012f8bf7061dbcaeaf61e3b6dd563d to your computer and use it in GitHub Desktop.
public static class TopologicalSorter
{
public static IEnumerable<T> Sort<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> dependsOn)
{
var sorted = new List<T>();
var visited = new HashSet<T>();
foreach (var item in source) Visit(item, visited, sorted, dependsOn);
return sorted;
}
private static void Visit<T>(T item, ISet<T> visited, ICollection<T> sorted, Func<T, IEnumerable<T>> dependsOn)
{
if (!visited.Contains(item))
{
visited.Add(item);
foreach (var dep in dependsOn(item)) Visit(dep, visited, sorted, dependsOn);
sorted.Add(item);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment