4
\$\begingroup\$

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 way too efficient compared to a recursive topological sort, or is it even wrong?

\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ > if there is a general method to solve them --> en.wikipedia.org/wiki/Topological_sorting \$\endgroup\$ – Koray Tugay Apr 20 at 15:34
  • \$\begingroup\$ @KorayTugay Ok, I was not so far, I see for example depth first search , but probably the choice of algorithm is depending from the context. \$\endgroup\$ – dariosicily Apr 20 at 15:42
  • \$\begingroup\$ Sorry, what do you mean you were not so far? \$\endgroup\$ – Koray Tugay Apr 20 at 15:51
  • \$\begingroup\$ @KorayTugay, I meant I thought about dfs because I think the problem is similar to find a path in a tree (excluding circular dependencies) where nodes are projects and edges are dependencies, but I never worked with it so mine is just an hypothesis. \$\endgroup\$ – dariosicily Apr 20 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.