Finding Build Order For Packages With Dependencies

Question

I gave a shot to infamous finding dependency problem. I highly encourage to give it a go yourself before seeing the solution I came up with.

Here is the problem statement:

Given a list of projects that need to be built and the dependencies for each, determine a valid order in which to build the packages.

Here is what I came up with:

Project.java

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Project {

    String id;

    Set<Project> dependencies = new HashSet<>();

    static Project withId(String id) {
        Project project = new Project();
        project.id = id;
        return project;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Project project = (Project) o;
        return Objects.equals(id, project.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return "Project{" + "id='" + id + '\'' + '}';
    }
}

BuildOrderResolver.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class BuildOrderResolver {

    List<Set<Project>> resolveOrder(Set<Project> projectsToBeOrdered) {
        List<Set<Project>> builderOrder = new ArrayList<>();

        Set<Project> buildableProjects = new HashSet<>();
        while (!projectsToBeOrdered.isEmpty()) {
            // These are the project we can build at this step
            Set<Project> projects = buildableProjects(projectsToBeOrdered, buildableProjects);

            // Could not resolve any project that can be built at this step
            if (projects.isEmpty()) {
                // But there are projects that still need resolve
                if (!projectsToBeOrdered.isEmpty()) {
                    // There is no possible build order
                    return null;
                }
            }

            projectsToBeOrdered.removeAll(projects);
            buildableProjects.addAll(projects);
            builderOrder.add(projects);
        }

        return builderOrder;
    }


    /**
     * Given all buildable projects so far, returns a Set of projects that can be built in this step
     */
    Set<Project> buildableProjects(Set<Project> projectsToBeOrdered, Set<Project> satisfiedProjects) {
        Set<Project> buildableProjects = new HashSet<>();

        projectsToBeOrdered.forEach(project -> {
            if (satisfiedProjects.containsAll(project.dependencies)) {
                buildableProjects.add(project);
            }
        });

        return buildableProjects;
    }
}

And this is a primitive test class I have:

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import static java.util.Arrays.asList;

public class BuildOrderTest {
    public static void main(String[] args) {
        BuildOrderResolver buildOrderResolver = new BuildOrderResolver();

        Project a, b, c, d, e, f;
        List<Set<Project>> buildOrder;


        // a -- depends on --> b
        a = Project.withId("a");
        b = Project.withId("b");
        a.dependencies.add(b);

        buildOrder = buildOrderResolver.resolveOrder(new HashSet<>(asList(a, b)));
        System.out.println(buildOrder);

        // a --> b --> c
        a = Project.withId("a");
        b = Project.withId("b");
        c = Project.withId("c");
        a.dependencies.add(b);
        b.dependencies.add(c);

        buildOrder = buildOrderResolver.resolveOrder(new HashSet<>(asList(a, b, c)));
        System.out.println(buildOrder);

        //          |--> b --|
        // c --> d--|        |--> f
        //          |--> a --|
        //
        //                        e (has no dependencies and no dependents)
        a = Project.withId("a");
        b = Project.withId("b");
        c = Project.withId("c");
        d = Project.withId("d");
        e = Project.withId("e");
        f = Project.withId("f");

        c.dependencies.add(d);
        d.dependencies.add(b);
        d.dependencies.add(a);
        b.dependencies.add(f);
        a.dependencies.add(f);

        buildOrder = buildOrderResolver.resolveOrder(new HashSet<>(asList(a, b, c, d, e, f)));
        System.out.println(buildOrder);

        // a <-- depends on --> b
        a = Project.withId("a");
        b = Project.withId("b");
        a.dependencies.add(b);
        b.dependencies.add(a);

        buildOrder = buildOrderResolver.resolveOrder(new HashSet<>(asList(a, b)));
        System.out.println(buildOrder);
    }
}

which spits out:

[[Project{id='b'}], [Project{id='a'}]]
[[Project{id='c'}], [Project{id='b'}], [Project{id='a'}]]
[[Project{id='e'}, Project{id='f'}], [Project{id='a'}, Project{id='b'}], [Project{id='d'}], [Project{id='c'}]]
null

After giving an attempt to this, I checked other answers online, which all look too complicated to me. Is my solution too inefficient compared to a recursive topological sort, or is it even wrong?

Answer 1

I rewrote some of your code, from your class Project:

public class Project {
    String id;
    Set<Project> dependencies = new HashSet<>();
    static Project withId(String id) {
        Project project = new Project();
        project.id = id;
        return project;
    }
     @Override
    public String toString() {
        return "Project{" + "id='" + id + '\'' + '}';
    }
}

You defined an implicit default constructor taking no arguments that means it is possible to define a project with naming it and a factory constructor taking one id argument, you can instead define a constructor taking as argument id and you can rewrite your toString method using String.format:

public class Project {

    private String id;
    private Set<Project> dependencies;

    public Project(String id) {
        this.id = id;
        this.dependencies = new HashSet<Project>();
    }

    @Override
    public String toString() {
        return String.format("Project{id='%s'}", id);
    }
}

I run your code without equals and hash methods and it is still fine.

I made some change to your method buildableProjects:

Set<Project> buildableProjects(Set<Project> projectsToBeOrdered, Set<Project> satisfiedProjects) {
    Set<Project> buildableProjects = new HashSet<>();

    projectsToBeOrdered.forEach(project -> {
        if (satisfiedProjects.containsAll(project.dependencies)) {
                buildableProjects.add(project);
            }
        });

    return buildableProjects;
}

You can use streams to abbreviate code:

Set<Project> buildableProjects(Set<Project> projectsToBeOrdered, Set<Project> satisfiedProjects) {

    return projectsToBeOrdered.stream()
            .filter(p -> satisfiedProjects.containsAll(p.getDependencies()))
            .collect(Collectors.toSet());
}

Your method List<Set<Project>> resolveOrder() instead of null for empty list can return Collections.emptyList()

I'm used junit to rewrite your class BuildOrderTest to have a division between cases you are examining , below the code of the class I have rewritten:

public class OrderTest {

    private BuildOrderResolver buildOrderResolver;
    private Project a, b, c, d, e, f;
    private List<Set<Project>> buildOrder;

    @BeforeEach
    void setUp() {
        buildOrderResolver = new BuildOrderResolver();
        a = new Project("a");
        b = new Project("b");
        c = new Project("c");
        d = new Project("d");
        e = new Project("e");
        f = new Project("f");
    }

    @Test
    void testAB() {
        a.getDependencies().add(b);
        buildOrder = buildOrderResolver.resolveOrder(new HashSet<>(asList(a, b)));
        System.out.println("testAB =" + buildOrder);
    }

    @Test
    void testABC() {
        a.getDependencies().add(b);
        b.getDependencies().add(c);
        buildOrder = buildOrderResolver.resolveOrder(new HashSet<>(asList(a, b, c)));
        System.out.println("testABC ="+ buildOrder);
    }

    @Test
    void testCDDBA() {
        c.getDependencies().add(d);
        d.getDependencies().add(b);
        d.getDependencies().add(a);
        b.getDependencies().add(f);
        a.getDependencies().add(f);

        buildOrder = buildOrderResolver.resolveOrder(new HashSet<>(asList(a, b, c, d, e, f)));
        System.out.println("testCDDBA ="+ buildOrder);
    }

    @Test
    void testCircularyDependency() {
        a.getDependencies().add(b);
        b.getDependencies().add(a);

        buildOrder = buildOrderResolver.resolveOrder(new HashSet<>(asList(a, b)));
        System.out.println("testCircularyDependency ="+ buildOrder);
    }
}

According to your description of the problem, it seems me really complicated to find a simple solution to this problem, it appears to me probably you should have to find a path in a graph without cycles with lot of costraints. If someone here had worked with this type of problems I'm curious too to see if there is a general method to solve them.