Created
June 18, 2016 15:15
-
-
Save Sup3rc4l1fr4g1l1571c3xp14l1d0c10u5/3341dba6a53d7171fe3397d13d00ee3f to your computer and use it in GitHub Desktop.
Topological Sorting (Kahn's algorithm) implemented in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
namespace TopologicalSort { | |
static class Program { | |
static void Main() { | |
// | |
// digraph G { | |
// "7" -> "11" | |
// "7" -> "8" | |
// "5" -> "11" | |
// "3" -> "8" | |
// "3" -> "10" | |
// "11" -> "2" | |
// "11" -> "9" | |
// "11" -> "10" | |
// "8" -> "9" | |
// } | |
var ret = TopologicalSort( | |
new HashSet<int>(new[] {7, 5, 3, 8, 11, 2, 9, 10}), | |
new HashSet<Tuple<int, int>>( | |
new [] { | |
Tuple.Create(7, 11), | |
Tuple.Create(7, 8), | |
Tuple.Create(5, 11), | |
Tuple.Create(3, 8), | |
Tuple.Create(3, 10), | |
Tuple.Create(11, 2), | |
Tuple.Create(11, 9), | |
Tuple.Create(11, 10), | |
Tuple.Create(8, 9) | |
} | |
) | |
); | |
System.Diagnostics.Debug.Assert(ret.SequenceEqual(new[] {7, 5, 11, 2, 3, 8, 9, 10})); | |
} | |
/// <summary> | |
/// Topological Sorting (Kahn's algorithm) | |
/// </summary> | |
/// <remarks>https://en.wikipedia.org/wiki/Topological_sorting</remarks> | |
/// <typeparam name="T"></typeparam> | |
/// <param name="nodes">All nodes of directed acyclic graph.</param> | |
/// <param name="edges">All edges of directed acyclic graph.</param> | |
/// <returns>Sorted node in topological order.</returns> | |
static List<T> TopologicalSort<T>(HashSet<T> nodes, HashSet<Tuple<T, T>> edges) where T : IEquatable<T> { | |
// Empty list that will contain the sorted elements | |
var L = new List<T>(); | |
// Set of all nodes with no incoming edges | |
var S = new HashSet<T>(nodes.Where(n => edges.All(e => e.Item2.Equals(n) == false))); | |
// while S is non-empty do | |
while (S.Any()) { | |
// remove a node n from S | |
var n = S.First(); | |
S.Remove(n); | |
// add n to tail of L | |
L.Add(n); | |
// for each node m with an edge e from n to m do | |
foreach (var e in edges.Where(e => e.Item1.Equals(n)).ToList()) { | |
var m = e.Item2; | |
// remove edge e from the graph | |
edges.Remove(e); | |
// if m has no other incoming edges then | |
if (edges.All(me => me.Item2.Equals(m) == false)) { | |
// insert m into S | |
S.Add(m); | |
} | |
} | |
} | |
// if graph has edges then | |
if (edges.Any()) { | |
// return error (graph has at least one cycle) | |
return null; | |
} else { | |
// return L (a topologically sorted order) | |
return L; | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
For anyone running this and seeing the
System.Diagnostics.Debug.Assert(ret.SequenceEqual(new[] {7, 5, 11, 2, 3, 8, 9, 10}));
throwing, the result is returning a slightly different result to the assertion, however it is still a valid solution, so it appears that the algorithm, at least how it is implemented here, is non-deterministic.