CODEWITHSUNDEEP
javac#.netalgorithmsorting
SuperJMN
SuperJMN

Reputation: 13992

Dependency sorting algorithm

I have a list of nodes like this

{ a, b , c }

with the dependencies between them defined as

The algorithm should return a sorted list so any given node should appear before any of its dependencies For instance, a valid solution would be: {c, b, a}

So far I have this class:

public static class DependencySorter
{
    public static ICollection<T> SortDependencies<T>(this IEnumerable<T> nodes) where T : IDependency<T>
    {
        var set = new HashSet<T>();

        foreach (var node in nodes)
        {
            foreach (var dependency in node.Resolve())
            {
                set.Add(dependency);
            }                
        }

        return set.ToList();
    }

    public static ICollection<T> Resolve<T>(this T node) where T : IDependency<T>
    {
        var resolved = new Collection<T>();
        ResolveDependenciesRecursive(node, resolved, new List<T>());
        return resolved;
    }

    private static void ResolveDependenciesRecursive<T>(T node, ICollection<T> resolved, ICollection<T> notResolved) where T : IDependency<T>
    {
        notResolved.Add(node);
        foreach (var edge in node.Dependencies.Where(edge => !resolved.Contains(edge)))
        {
            if (notResolved.Contains(edge))
            {
                throw new InvalidOperationException($"Circular dependency detected {node} => {edge}");
            }

            ResolveDependenciesRecursive(edge, resolved, notResolved);
        }

        resolved.Add(node);
        notResolved.Remove(node);
    }
}

public interface IDependency<out T>
{
    IEnumerable<T> Dependencies { get; }
}

I'm sure that its performance and complexity is really bad.

Upvotes: 1

Views: 2624

Answers (1)

DrWatson
DrWatson

Reputation: 418

This is called "topological sorting". There are some efficient and relatively simple algorithms available (Wikipedia lists some), typically in O(|V|+|E|) time. My favorite is the one based on depth-first search:

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 

function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

(This is a copy & paste from https://en.wikipedia.org/wiki/Topological_sorting)

Upvotes: 5

Related Questions