Skip to content

Instantly share code, notes, and snippets.

@yet-another-alexander

yet-another-alexander/TopologicalSorter.cs

Last active July 13, 2018 16:22
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save yet-another-alexander/0009748f2c0dec1e867e358e5f0d4397 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save yet-another-alexander/0009748f2c0dec1e867e358e5f0d4397 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Alexander Ivanov revised this gist Jul 13, 2018. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion TopologicalSorter.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -4,7 +4,7 @@
    using System.Text;
    using System.Threading.Tasks;

    namespace Ego3.GameDb.Utilities
    namespace Application
    {
    public static class TopologicalSorter
    {
  2. Alexander Ivanov created this gist Jul 13, 2018.
    54 changes: 54 additions & 0 deletions TopologicalSorter.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,54 @@
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace Ego3.GameDb.Utilities
    {
    public static class TopologicalSorter
    {
    /// <summary>
    /// Returns a set of items sorted by topological order.
    /// </summary>
    /// <typeparam name="T">The element type of the sequence.</typeparam>
    /// <param name="source">The source.</param>
    /// <param name="dependencies">The dependencies.</param>
    /// <param name="throwOnCycle">If set to <c>true</c> cyclic dependency is not allowed.</param>
    /// <returns>The sorted sequence.</returns>
    public static IEnumerable<T> TplgSort<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) == false)
    {
    visited.Add(item);

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

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