public static class DependencySorter<T>
{
public static IEnumerable<T> Sort(Dictionary<T, IEnumerable<T>> dependencies)
{
var visited = new Dictionary<T, bool>();
foreach (var key in dependencies.Keys)
{
visited[key] = false;
}
foreach (var key in dependencies.Keys)
{
foreach (var ordered in Search(key, dependencies, visited))
yield return ordered;
}
}
private static IEnumerable<T> Search
(
T key,
IDictionary<T, IEnumerable<T>> dependencies,
IDictionary<T, bool> visited
)
{
if (!visited[key])
{
visited[key] = true;
foreach (T value in dependencies[key])
{
foreach (var ordered in Search(value, dependencies, visited))
{
yield return ordered;
}
}
yield return key;
}
}
}
Refactorings
No refactoring yet !
rikkus
November 5, 2008, November 05, 2008 12:16, permalink
Simple demo program.
foreach (var item in
DependencySorter<int>.Sort
(
new Dictionary<int, IEnumerable<int>>
{
{5, new int[] {4, 3, 2}},
{2, new int[] {1}},
{1, new int[] {}},
{4, new int[] {3}},
{3, new int[] {1, 2}}
}
)
)
{
Console.WriteLine(item);
}
Moonshield
November 5, 2008, November 05, 2008 23:18, permalink
I'd like to help but I'm not sure to understand what you try to achieve. Can you provide more details or provide a new Dictionnary to test with that produce something else then 1,2,3,4,5 when you execute it, it would help me to understand.
rikkus
November 6, 2008, November 06, 2008 11:31, permalink
The real world scenario is adding user-defined functions to a SQL Server database.
The functions must be created in order, such that when a function is created, the ones upon which it depends (those which it calls) have already been created.
For example: I may write a function Foo which calls another function Bar. Function Bar must be created before I can create Foo, or the compiler will complain.
The data structure expected as input by this (genericised) algorithm is a set of references to nodes, each paired with a collection of references to nodes upon which it depends.
This code sorts a collection by the dependencies of its contents.
It is passed a dictionary mapping a key to a set of keys - the dependencies of that key.
I knocked up this code quickly and realised as I wrote it that it was likely to blow the stack on a large data set due to its recursive nature. I'd try to make it tail recursive, but the C# compiler doesn't take advantage of that yet, so it should probably be iterative. I'd be interested to see any improved solution.