Create a build order from a list of projects and their respective prerequisites

Question

Another graph algorithm, this time to create a priority or build order. Provided with a starting List<Project> and List<ProjectWithPrerequisite> the algorithm will return the order to build them in. For a list of projects a, b, c, d, e, f and their corresponding prerequisites where a, d means that a is a prerequisite for d or a-->d.

To find the build order, projects are sorted in descending prerequisite order so that projects with the most prerequisites come first. Each project has a path created for every prerequisite up until the starting node is found, which has no prerequisites. Projects with multiple prerequisites, and subsequent multiple paths, have these paths merged into a single path for the build order of that project. Once the linear path has been created for the project it is added to a completed order list.

To avoid repeatedly searching the same path I check if a Project already belongs to the completed order and if so stop checking since it will already have its itself and precedents as members.

I have not considered the scenarios where:

• All projects have prerequisites which forms a loop with itself. A-->B-->C-->A
• There are two or more non-connected paths (islands) for the same project.

Included at the end are the unit tests I used.

How can I improve my logic? Does anything stand out as excessively complex or not straightforward enough?

public class Project
{
    public List<Project> Prerequisites { get; } = new List<Project>();
    public char Name { get; }

    public Project(char name)
    {
        Name = name;
    }
}

public class ProjectWithPrerequisite
{
    public Project Project { get; }
    public Project Prerequisite { get; }

    public ProjectWithPrerequisite(Project prerequisite, Project project)
    {
        Prerequisite = prerequisite;
        Project = project;            
    }
}

public class ProjectBuildOrder
{
    private Dictionary<char, Project> _projects { get; }
    private List<ProjectWithPrerequisite> _singlePrerequisites { get; }
    private List<Project> _completedOrder = new List<Project>();

    public ProjectBuildOrder(List<Project> projects, List<ProjectWithPrerequisite> singlePrerequisites)
    {
        _projects = new Dictionary<char, Project>(projects.Count);
        foreach (var item in projects)
        {
            _projects.Add(item.Name, item);
        }

        _singlePrerequisites = singlePrerequisites;
    }

    /// <summary>
    /// Creates the build order to accomplish the given list of projects.
    /// </summary>
    /// <returns></returns>
    public List<Project> GenerateBuildOrder()
    {
        AddPrerequisitesToProjects();

        return BuildOrder();
    }

    /// <summary>
    /// Adds the provided prerequisites to the projects.
    /// </summary>
    private void AddPrerequisitesToProjects()
    {
        foreach (var pair in _singlePrerequisites)
        {
            var projectWithPrerequisite = _projects[pair.Project.Name];

            projectWithPrerequisite.Prerequisites.Add(pair.Prerequisite);
        }
    }

    /// <summary>
    /// Creates the build order for the list of <see cref="Project"/>s.
    /// </summary>
    /// <returns><see cref="List{T}"/> containing the build order for the provided list of <see cref="Project"/>s and their prerequisites.</returns>
    private List<Project> BuildOrder()
    {
        var checkOrder = _projects
            .OrderByDescending(kvp => kvp.Value.Prerequisites.Count).Select(kvp => kvp.Value);

        _completedOrder = new List<Project>();
        var path = new LinkedList<Project>();
        foreach (var project in checkOrder.Where(p => !_completedOrder.Contains(p)))
        {
            if (project.Prerequisites.Count > 1)
            {
                var branchPaths = GetBranchPrecedents(project);
                path = MergePaths(branchPaths);
            }
            else
            {
                path = NonBranchingPath(project);
            }

            _completedOrder.AddRange(path.Where(p => !_completedOrder.Contains(p)));
        }

        return _completedOrder;
    }

    /// <summary>
    /// For a node which has only a single prerequisite. This will follow the path back to the end, branching if necessary by claling <see cref="GetBranchPrecedents(Project)"/>.
    /// </summary>
    /// <param name="project">The node whose precedents will be listed.</param>
    /// <returns></returns>
    private LinkedList<Project> NonBranchingPath(Project project)
    {
        if (project.Prerequisites.Count == 0)
        {
            var ll = new LinkedList<Project>();
            ll.AddLast(project);
            return ll;
        }

        if (project.Prerequisites.Count == 1)
        {
            var ll = new LinkedList<Project>();
            ll.AddLast(project);
            var parent = project.Prerequisites[0];

            if (_completedOrder.Contains(parent))
            {
                return ll;
            }

            while (parent.Prerequisites.Count == 1)
            {
                ll.AddFirst(parent);
                parent = parent.Prerequisites[0];

                if (_completedOrder.Contains(parent))
                {
                    break;
                }
            }

            if (parent.Prerequisites.Count == 0)
            {
                if (!_completedOrder.Contains(parent))
                {
                    ll.AddFirst(parent);
                }
                    
                return ll;
            }

            var parentPath = MergePaths(GetBranchPrecedents(parent));
            var first = ll.First.Value;
            ll.RemoveFirst();
            parentPath.AddLast(first);
            return parentPath;
        }

        return MergePaths(GetBranchPrecedents(project));
    }

    /// <summary>
    /// When a node contains multiple prerequisites it will follow each path. If a prerequisite path branches it will recursively
    /// call itself to find those branching paths, and merging them.
    /// </summary>
    /// <param name="projectForPrerequisite">Node containini more than one prerequisite.</param>
    /// <returns><see cref="List{T}"/> containing the distinct path branches.</returns>
    private List<LinkedList<Project>> GetBranchPrecedents(Project projectForPrerequisite)
    {
        var list = new List<LinkedList<Project>>();
        foreach (var parent in projectForPrerequisite.Prerequisites.Where(project => !_completedOrder.Contains(project)))
        {
            switch (parent.Prerequisites.Count)
            {
                case 0:
                    var endOfPrecedenceChain = new LinkedList<Project>();
                    endOfPrecedenceChain.AddFirst(parent);
                    endOfPrecedenceChain.AddLast(projectForPrerequisite);                        
                    list.Add(endOfPrecedenceChain);
                    break;
                case 1:
                    var nonBranch = NonBranchingPath(parent);
                    nonBranch.AddLast(projectForPrerequisite);
                    list.Add(nonBranch);
                    break;
                default:
                    var branchPrecedents = GetBranchPrecedents(parent);
                    var mergedPrecedents = MergePaths(branchPrecedents);
                    mergedPrecedents.AddLast(parent);
                    mergedPrecedents.AddLast(projectForPrerequisite);
                    list.Add(mergedPrecedents);
                    break;
            }
        }
        return list;
    }

    /// <summary>
    /// Merge each of the branching paths in the <see cref="LinkedList{T}"/> into one. Merging based on precedence they were added.
    /// </summary>
    /// <param name="paths">A <see cref="List{T}"/> containing the branching paths.</param>
    /// <returns><see cref="LinkedList{T}"/> of path back to a starting node which has no prerequisites.</returns>
    LinkedList<Project> MergePaths(List<LinkedList<Project>> paths)
    {
        if (paths.Count == 1)
        {
            return paths[0];
        }
                        
        var last = paths[0].Last.Value;
        var merged = paths[0];
        merged.RemoveLast();
            
        LinkedList<Project> ll;
        for (int path = 1; path < paths.Count; path++)
        {
            ll = paths[path];
            ll.RemoveLast();
            while (ll.Any())
            {
                if (!merged.Contains(ll.First.Value))
                {
                    merged.AddLast(ll.First.Value);
                }

                ll.RemoveFirst();
            }
        }

        merged.AddLast(last);

        return merged;
    }
}

Unit tests to check results against.

[Fact]
public void Single_branch_list_follows_build_order()
{
    #region All_projects
    var a = new Project('a');
    var b = new Project('b');
    var c = new Project('c');
    var d = new Project('d');
    var e = new Project('e');
    var f = new Project('f');
    #endregion

    var expected = new List<Project>() { f, a, b, d, c, e };

    var projects = new List<Project>() { a, b, c, d, e, f };

    var projectsAndPrerequisite = new List<ProjectWithPrerequisite>() 
    {
        new ProjectWithPrerequisite(a, d), 
        new ProjectWithPrerequisite(f, b), 
        new ProjectWithPrerequisite(b, d), 
        new ProjectWithPrerequisite(f, a), 
        new ProjectWithPrerequisite(d, c) 
    };

    var sut = new ProjectBuildOrder(projects, projectsAndPrerequisite);

    var actual = sut.GenerateBuildOrder();

    Assert.Equal(expected, actual);
}

[Fact]
public void Multi_branch_list_follows_build_order()
{
    #region All_projects
    var a = new Project('a');
    var b = new Project('b');
    var c = new Project('c');
    var d = new Project('d');
    var e = new Project('e');
    var f = new Project('f');
    var g = new Project('g');
    #endregion

    var expected = new List<Project>() { g, f, a, b, d, c, e };

    var projects = new List<Project>() { a, b, c, d, e, f, g };

    var projectsAndPrerequisite = new List<ProjectWithPrerequisite>()
    {
        new ProjectWithPrerequisite(g, c),
        new ProjectWithPrerequisite(a, d),
        new ProjectWithPrerequisite(f, b),
        new ProjectWithPrerequisite(b, d),
        new ProjectWithPrerequisite(f, a),
        new ProjectWithPrerequisite(d, c)
    };

    var sut = new ProjectBuildOrder(projects, projectsAndPrerequisite);

    var actual = sut.GenerateBuildOrder();

    Assert.Equal(expected, actual);
}

[Fact]
public void Multi_branch_list_has_prerequisites_sorted_in_alphabetical_order()
{
    #region All_projects
    var a = new Project('a');
    var b = new Project('b');
    var c = new Project('c');
    var d = new Project('d');
    var e = new Project('e');
    var f = new Project('f');
    var g = new Project('g');
    #endregion

    var expected = new List<Project>() { f, g, b, a, d, c, e };

    var projects = new List<Project>() { a, b, c, d, e, f, g };

    var projectsAndPrerequisite = new List<ProjectWithPrerequisite>()
    {
        new ProjectWithPrerequisite(g, b),
        new ProjectWithPrerequisite(g, c),
        new ProjectWithPrerequisite(a, d),
        new ProjectWithPrerequisite(f, b),
        new ProjectWithPrerequisite(b, d),
        new ProjectWithPrerequisite(f, a),
        new ProjectWithPrerequisite(d, c),
        new ProjectWithPrerequisite(f, g),
    };

    var sut = new ProjectBuildOrder(projects, projectsAndPrerequisite);

    var actual = sut.GenerateBuildOrder();

    Assert.Equal(expected, actual);
}

Answer 1

Algorithm

Correctness

Due to a small problem in GetBranchPrecedents this algorithm does not actually work. The case that all parents might already be present in the complete order. E.g. take the graph with the edges (C,A), (D,A), (E,A), (D,B), (E,B). In this case, A has the most prerequisites and will be treated first. This puts all nodes but B into the order. Since B has more than one prerequisite, the branch using GetBranchPrecedents is used, where no parent will be evaluated because they are all already in the complete order.

This can easily be fixed by treating this special case inside GetBranchPrecedents or by making the function better honor its name and adding the final node for the project in question outside of it.

Design and Documentation

The design of the algorithm seems to be a bit convoluted. This seems to partly originate in a lack of documentation of NonBranchingPath's purpose. As far as I can see, it is simply a performance optimization to avoid merging single element lists of ancestor paths. This would also explain the switch from a recursive approach to the inclusion of iterative parts. The algorithm itself could have been written entirely without special-casing single parents.

Performance

The asymptotic complexity of this algorithm is rather bad. It is at least never better than O(V^2) but might as well only be O(V^3), where V is the number of projects (vertices); I have not performed a thorough analysis.

The first problem is that the check whether a project already exists in the final order is performed by a Contains on the list containing the final order. Each of these checks is an O(V) operation. By maintaining a HashSet of the already sorted projects, this could be essentially reduced to O(1).

The second problem is that MergePaths may have to revisit the same nodes a lot and that the Contains check here is on a linked list. The check could be optimized by maintaining a HashSet again. However, there is no easy solution for the other problem. E.g. take a chain of n nodes one depending on the next; let the last one depend on n other nodes, which all depend on one final node. All descendant paths for the final node will contain the first n nodes. Thus, this step is at least quadratic in the number of nodes, even when the number of edges is linear in the number of nodes.

Finally, sorting the elements at the start is not really necessary and leads to a minimum complexity of O(V*log(V)), no matter how few edges there are.

Alternatives

There is an alternative approach to this problem, which is also known as topological sorting, that is a bit easier to follow and at the same time achieves an asymptotic complexity of O(V+E), where V is the number of projects and E the number of prerequisites. I do not want to spoil the answer to how it works here, though. (You can just search for topological sort, if you do not want to figure it out yourself.) I will just give the hint that you should think about which nodes you can add at the start or the build order and what you have to maintain to let the problem look the same, just for a smaller list of projects, after you have added the first element.

API

To me, the API is a bit confusing, i.e. the publicly accessible features to not follow a clear line and impose some restrictions, which are not really needed.

The first thing that confused me a bit was that you have a separate class for the dependency edges, while the projects already contains that information. In addition, your functionality takes in both projects and dependencies at the same time. This is confusing because it is not clear which of the dependency information will be taken into account.

I see two ways to make this clearer: either remove the dependency input entirely or remove the dependencies from the projects. In both cases, only one source of dependencies remains ant the API is clearer. In the latter case, you could maintain the dependencies of project information in a dictionary.

You Project classes expose a bit much functionality to the public. All they really need to expose regarding the dependencies is an IReadOnlyCollecion<Project> and a method AddDependency or an ICollection<Project>, if you want to allow deleted as well. There is really no value in the order of the dependencies here. Should that be important for some other external reason, at least consider using the interface IList instead of fixing the concrete implementation.

On a similar note, the constructor for ProjectBuildOrder could just take IEnumerable<T> instances since you just iterate over them once.

In addition, the whole class ProjectBuildOrder would probably be better off as a function or as a strategy class with a single function taking in the current constructor parameters as its parameters. There is no real benefit here in maintaining any information on the class level, except maybe convenience. If information was passed around in a more functional way, it would be possible to use this algorithm on multiple threads in parallel.

Finally, the return type of GenerateBuildOrder could be an IList<Project> and should probably be better names BuildOrder. In general, when naming methods, procedures should be verbs describing what they do and functions and properties should be nouns describing the result.

General

I will not write too much in this category, since the review is already long enough. However, I would like to point out that the naming of variables could be improved a bit. In general, it tries to state what the things are, but then slips a bit, which can become confusing. One example of this is the loop variable path in MergePaths, which really should be pathIndex because ll is the actual path. Moreover, using ll for the linked lists everywhere wastes the opportunity to state what the linked list represents. In general, name things after what they represent, not after what they technically are.