-
-
Save Sup3rc4l1fr4g1l1571c3xp14l1d0c10u5/3341dba6a53d7171fe3397d13d00ee3f to your computer and use it in GitHub Desktop.
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; | |
} | |
} | |
} | |
} |
Thanks for implementation, now I can understand the algorithm much better. 🙂
This line is a O(NxM) operation. (N = nodes.Count, M = edges.Count). This is the performance issue when N and M are big.
var S = new HashSet<T>(nodes.Where(n => edges.All(e => e.Item2.Equals(n) == false)));
Choose one of these optimal implemented algorithms (Kahn and DFS): https://www.geeksforgeeks.org/kahns-algorithm-vs-dfs-approach-a-comparative-analysis/
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.
really great stuff.. keep going..