Recently I wrote about directed acyclic graphs, and how you can derive topological orderings from them. Now let’s look at a more practical example.

Gradle is a build tool. It is built on tasks.

There are dependencies among the tasks (i.e. we can’t build if we haven’t run compileJava). Instead of just storing a linked list type structure in which we do the tasks, Gradle internally stores the dependency graph as a DAG.

To illustrate this example, I have a demo Spring Boot application, with dependencies in Spring MVC & Tomcat (web). I also made it a Kotlin project. Other than that, it’s the standard application the Spring Initializr will generate.

Let’s look at a section of the graph (technically everything needed to run assemble, which is one of the two tasks needed for gradle build to run (the other being test)).

TLDR – a gradle task is a single atomic piece of work for a build, such as compiling classes or generating javadoc.

Now, if we want to get a valid order in which to run the tasks (Gradle does this internally), we need to topologically sort the DAG.

tsort <<EOF
  compileKotlin compileJava
  compileKotlin jar
  compileKotlin bootJar
  compileJava classes
  processResources classes
  classes bootJar
  classes jar
  classes inspectClassesForKotlinIC
  inspectClassesForKotlinICjar
  jar assemble
  bootJar assemble
EOF

And the result is a valid order in which to run the tasks:

processResources
compileKotlin
compileJava
classes
bootJar
inspectClassesForKotlinIC
jar
assemble

As we said, Gradle has to topologically sort the DAG internally. In order to see it’s linear ordering, run gradle assemble -m.

:compileKotlin SKIPPED
:compileJava SKIPPED
:processResources SKIPPED
:classes SKIPPED
:bootJar SKIPPED
:inspectClassesForKotlinIC SKIPPED
:jar SKIPPED
:assemble SKIPPED

BUILD SUCCESSFUL in 0s

It is different, but only slightly. Recall that topological orderings are not unique (there are multiple ways to put your clothes on in the morning).