Make utility using LINQ

Question

Make() takes projects with a list of tuples representing project references in the form of (Dependency, Dependent) and returns projects in the order to be build:

static void Main(string[] args)
{
    var projects = new[] { "a", "b", "c", "d", "e", "f" };
    var dependencies = new[] { ("a", "b"), ("a", "c"), ("e", "f"), ("c", "f"), ("f", "d") };
    Console.WriteLine(
        string.Join(", ", Make(projects, dependencies))); // a, e, b, c, f, d
}

Where:

static IEnumerable<string> Make(
    IEnumerable<string> projects, 
    IEnumerable<(string Dependency, string Dependent)> references)
{
    var dependents = new HashSet<string>(references.Select(d => d.Dependent));
    var build = new HashSet<string>(projects.Except(dependents));
    return 
        !projects.Any() ? Enumerable.Empty<string>() :
        !build.Any() ? throw new Exception("Circled references detected.") :
        build.Concat(Make(
            projects.Except(build).ToArray(),
            references.Where(r => !build.Contains(r.Dependency)).ToArray()));
}

What about run-time complexity of this one? Could it be optimized?

Answer 1

Exit early

Instead of stuffing everything in one return statements, return as early as possible.

if (!projects.Any()) return Enumerable.Empty<string>();

can be the first statement of your method. It saves recreating the hashset objects and it makes the flow of your method with its recursion more clear. I think sacrificing a bit of "conciseness" for readability is worth it.

ToArray

Are unnecessary and cause additional loops over your sets.

Except and HashSet

Enumerable.Except is already implemented using sets. The second argument is added to a set and the first is streamed through it. Creating the HashSet manually is a wasted effort. See the reference source.

So dependents can just be:

var dependents = references.Select(d => d.Dependent);

Contains and HashSet

Contains on the other hand benefits from the HashSet overload, since the Enumerable.Contains implementation just loops over the sequence. So build should be a HashSet to cope with larger inputs. While we're at it, we're using Linq, so ToHashSet().

static IEnumerable<string> Make(
    IEnumerable<string> projects,
    IEnumerable<(string Dependency, string Dependent)> references)
{
    if (!projects.Any())
    {
        return Enumerable.Empty<string>();
    }
    var dependents = references.Select(d => d.Dependent);
    var build = projects.Except(dependents).ToHashSet();
    if (!build.Any())
    {
        throw new Exception("Circled references detected.");
    }
    else
    {
        return build.Concat(Make(
              projects.Except(build),
              references.Where(r => !build.Contains(r.Dependency))));
    }
}