Мне не нравятся рекурсивные методы, поэтому DMM отсутствует.Krumelur выглядит хорошо, но, кажется, использует много памяти?Сделал альтернативный метод на основе стека, который, кажется, работает.Использует ту же логику DFS, что и DMM, и я использовал это решение в качестве сравнения при тестировании.
public static IEnumerable<T> TopogicalSequenceDFS<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> deps)
{
HashSet<T> yielded = new HashSet<T>();
HashSet<T> visited = new HashSet<T>();
Stack<Tuple<T, IEnumerator<T>>> stack = new Stack<Tuple<T, IEnumerator<T>>>();
foreach (T t in source)
{
stack.Clear();
if (visited.Add(t))
stack.Push(new Tuple<T, IEnumerator<T>>(t, deps(t).GetEnumerator()));
while (stack.Count > 0)
{
var p = stack.Peek();
bool depPushed = false;
while (p.Item2.MoveNext())
{
var curr = p.Item2.Current;
if (visited.Add(curr))
{
stack.Push(new Tuple<T, IEnumerator<T>>(curr, deps(curr).GetEnumerator()));
depPushed = true;
break;
}
else if (!yielded.Contains(curr))
throw new Exception("cycle");
}
if (!depPushed)
{
p = stack.Pop();
if (!yielded.Add(p.Item1))
throw new Exception("bug");
yield return p.Item1;
}
}
}
}
Здесь также представлен более простой вариант BFS на основе стека.Результат будет отличаться от указанного выше, но все еще действителен.Я не уверен, есть ли какое-либо преимущество в использовании варианта DFS, описанного выше, но было интересно создать его.
public static IEnumerable<T> TopologicalSequenceBFS<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies)
{
var yielded = new HashSet<T>();
var visited = new HashSet<T>();
var stack = new Stack<Tuple<T, bool>>(source.Select(s => new Tuple<T, bool>(s, false))); // bool signals Add to sorted
while (stack.Count > 0)
{
var item = stack.Pop();
if (!item.Item2)
{
if (visited.Add(item.Item1))
{
stack.Push(new Tuple<T, bool>(item.Item1, true)); // To be added after processing the dependencies
foreach (var dep in dependencies(item.Item1))
stack.Push(new Tuple<T, bool>(dep, false));
}
else if (!yielded.Contains(item.Item1))
throw new Exception("cyclic");
}
else
{
if (!yielded.Add(item.Item1))
throw new Exception("bug");
yield return item.Item1;
}
}
}
Для .NET 4.7+ я предлагаю заменить Tuple на ValueTuple для более низкого использования памяти.В более старых версиях .NET Tuple можно заменить на KeyValuePair.