Dependency sorting algorithm

Question

I have a list of nodes like this

{ a, b , c }

with the dependencies between them defined as

a => { b, c }
b => { c }
c => { }

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.

And what have you tried so far? Also this problem might not be terribly straightforward if you need to consider things such as circular dependencies. — CollinD
– CollinD, Commented Sep 23, 2015 at 22:07

DrWatson · Accepted Answer · 2015-09-23 22:10:56Z

5

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)

answered Sep 23, 2015 at 22:10

DrWatson

4183 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

SuperJMN Over a year ago

Could you please translate it to C# or Java :) Thanks!

Eric J. Over a year ago

@SuperJMN: Why don't you take your best stab at translating it. If you get stuck, ask a new question.

SuperJMN Over a year ago

Thank you. I was in a hurry, so I wanted a ready-to-use version. Thank you!

Poscat Over a year ago

What if the dependency graph is cyclic?

Brian Cannard Over a year ago

Then the problem is NP-complete. It's perfectly fine. Node.js does, so you can do.

Collectives™ on Stack Overflow

Dependency sorting algorithm

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related