Dependency builder that tracks circular dependencies and duplicates

DependencyBuilder.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace Icm
{
    public class Dependency<T> where T : class
    {
        public Dependency(T node, T parent = null, IEnumerable<T> dependencies = null)
        {
            Node = node;
            Parent = parent;
            Dependencies = dependencies ?? new List<T>();
        }

        public T Node { get; }
        public T Parent { get; }
        public IEnumerable<T> Dependencies { get; }

        public override string ToString()
        {
            return $"DEP {Node} PAR {Parent} DEPS {string.Join(",", Dependencies.Select(x => x.ToString()))}";
        }
    }

    public class DependencyBuilder<T> where T : class
    {
        private readonly Func<T, IEnumerable<T>> _directDependencyFunc;
        private readonly IEqualityComparer<Dependency<T>> _equalityComparer;

        private class DepComparer : IEqualityComparer<Dependency<T>>
        {
            private readonly IEqualityComparer<T> _equalityComparer;

            public DepComparer(IEqualityComparer<T> equalityComparer)
            {
                _equalityComparer = equalityComparer;
            }

            public bool Equals(Dependency<T> x, Dependency<T> y)
            {
                return _equalityComparer.Equals(x.Node, y.Node);
            }

            public int GetHashCode(Dependency<T> obj)
            {
                return _equalityComparer.GetHashCode(obj.Node);
            }
        }

        public DependencyBuilder(
            Func<T, IEnumerable<T>> directDependencyFunc,
            IEqualityComparer<T> equalityComparer = null)
        {
            _directDependencyFunc = directDependencyFunc;
            _equalityComparer = new DepComparer(equalityComparer ?? new DefaultComparer());
        }

        public IEnumerable<Dependency<T>> Build(params T[] jobs)
        {
            return jobs.SelectMany(job => BuildAux(job))
                .Distinct(_equalityComparer);
        }

        public IEnumerable<Dependency<T>> Build(T job)
        {
            return Build(new[] { job });
        }

        private IEnumerable<Dependency<T>> BuildAux(T job, IEnumerable<T> ancestors = null)
        {
            var deps = _directDependencyFunc(job).ToList();
            var ancestorsList = ancestors?.ToList() ?? new List<T>();
            if (!deps.Any())
            {
                yield return new Dependency<T>(job, ancestorsList.LastOrDefault(), new List<T>());
            }

            if (deps.Any(ancestorsList.Contains))
            {
                throw new Exception("Circular dependency!!");
            }

            var recursive = deps
                .SelectMany(dep => 
                    BuildAux(dep, ancestorsList.Concat(new[] { job })));

            foreach (var dep in recursive)
            {
                yield return dep;
            }

            yield return new Dependency<T>(job, ancestorsList.LastOrDefault(), deps);
        }

        private class DefaultComparer: IEqualityComparer<T>
        {
            public bool Equals(T x, T y)
            {
                return x.Equals(y);
            }

            public int GetHashCode(T obj)
            {
                return obj.GetHashCode();
            }
        }
    }
}

DependencyBuilderTests.cs

using System;
using System.Linq;
using FluentAssertions;
using Icm;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace Conveyor.API.Tests
{
    [TestClass]
    public class DependencyBuilderTests
    {
        [TestMethod]
        public void Build_NoProblems_Success()
        {
            var depBuilder = new DependencyBuilder<string>(
                job =>
                {
                    switch (job)
                    {
                        case "A":
                            return new[]
                            {
                                "C",
                                "B"
                            };
                        case "B":
                            return new[]
                            {
                                "D",
                                "E"
                            };
                        default:
                            return new string[0];
                    }
                });

            var deps = depBuilder.Build("A").ToList();

            deps.ShouldBeEquivalentTo(new[]
            {
                new Dependency<string>("C", "A"),
                new Dependency<string>("D", "B"),
                new Dependency<string>("E", "B"),
                new Dependency<string>("B", "A", new [] { "D", "E" }),
                new Dependency<string>("A", null, new [] { "C", "B" })
            }, options => options.WithStrictOrdering());
        }

        [TestMethod]
        public void Build_CircularDependency_Throws()
        {
            var depBuilder = new DependencyBuilder<string>(
                job =>
                {
                    switch (job)
                    {
                        case "A":
                            return new[]
                            {
                                "C",
                                "B"
                            };
                        case "B":
                            return new[]
                            {
                                "D",
                                "A"
                            };
                        default:
                            return new string[0];
                    }
                });

            Action action = () => depBuilder.Build("A").ToList();

            action.ShouldThrow<Exception>();
        }

        [TestMethod]
        public void Build_Duplicates_Removed()
        {
            var depBuilder = new DependencyBuilder<string>(
                job =>
                {
                    switch (job)
                    {
                        case "A":
                            return new[]
                            {
                                "C",
                                "B"
                            };
                        case "B":
                            return new[]
                            {
                                "D",
                                "C"
                            };
                        case "C":
                            return new[]
                            {
                                "E",
                                "F"
                            };
                        default:
                            return new string[0];
                    }
                });

            var deps = depBuilder.Build("A").ToList();

            deps.ShouldBeEquivalentTo(new[]
            {
                new Dependency<string>("E", "C"),
                new Dependency<string>("F", "C"),
                new Dependency<string>("C", "A",  new [] { "E", "F" }),
                new Dependency<string>("D", "B"),
                new Dependency<string>("B", "A",  new [] { "D", "C" }),
                new Dependency<string>("A", null, new [] { "C", "B" })
            }, options => options.WithStrictOrdering());
        }

        [TestMethod]
        public void Build2_Duplicates_Removed()
        {
            var depBuilder = new DependencyBuilder<string>(
                job =>
                {
                    switch (job)
                    {
                        case "B":
                            return new[]
                            {
                                "C"
                            };
                        case "C":
                            return new[]
                            {
                                "A"
                            };
                        default:
                            return new string[0];
                    }
                });

            var deps = depBuilder.Build("B", "A").ToList();

            deps.ShouldBeEquivalentTo(new[]
            {
                new Dependency<string>("A", "C"),
                new Dependency<string>("C", "B",  new [] { "A" }),
                new Dependency<string>("B", null,  new [] { "C" }),
            }, options => options.WithStrictOrdering());
        }
    }

}