Acyclic Dependencies Principle

Cycled components can only be used together. They can only be tested, reused, deployed and understood together. The bad thing with cycles is that every node on a cycle depends on any other. Having lots of cycles lets explode the number of indirect dependencies within the system. Without early intervention, the system starts to rot.

We should therefore avoid dependency cycles within the design layer. That is, no library, package or package tree dependency cycles! This is known as the Acyclic Dependencies Principle.

Cycles

Let's assume we have cyclic dependencies and want to remove them. Therefore, we want to do some refactoring that modifies our dependency graph to be acyclic. A naive approach would be to list all cycles, break them, one by one, until no cycles are left. Breaking a cycle could be done by removing or reversing a dependency. Let's see how that works.

Cycled GraphConsider a graph with all pairs of nodes connected by edges into both directions. If we have two nodes, there's exactly one cycle. Adding a third node, we get five cycles: three cycles between pairs of nodes and two cycles containing all three nodes, clockwise and counterclockwise. Now let's increase the number of nodes to – say – ten. Guess how many cycles we get? More than a million! Seems like we better abandon the idea of fiddling around with individual cycles...

Tangles

A Tangle is a subgraph with at least two nodes, where each node is reachable from each other. It is a tangle, where our cycles live. Every cycle lies in a tangle and every tangle consists of just cycles. In other words: A graph is acyclic if and only if it has no tangles.

Instead of breaking individual cycles, we could try to break tangles! Breaking a tangle means to transform it into an acyclic graph.

However, the edges in STAN's dependency graphs are weighted with the number of underlying code dependencies. Obviously, it is easier to remove or reverse a light edge than a heavy one. Therefore, we should select a minimum weight set of edges to break our tangle.

In graph theory, this is known as a Minimum Feedback (Arc) Set. The minimum feedback set is the “predetermined breaking point” of a tangle. Or, from another point of view, the minimum feedback set contains the edges, that point into the “wrong” direction. Feedback edges are the primary key to the elimination of cyclic dependencies.

Tangled GraphSTAN's graph layout algorithm takes this into account: in a dependency graph, edges from the minimum feedback set point into the opposite direction than other edges. Additionally, for design tangles, these edges are colored red.

When looking at a tangled graph, it's often hard to identify the boundaries of a tangle. Its nodes may be spread over the graph, so it's sometimes difficult to see which nodes and edges make up the tangle.

Partitioned GraphWith STAN, you can partition dependency graphs into tangles. This isolates tangles by making them compound nodes. Note that the partition graph itself is acyclic: all cycles have been moved into the tangle nodes. This presentation is optimal to focus on cyclic dependencies.

As a side effect, it also reduces the complexity of  the graph, because edges between nodes inside and outside of a tangle have been cumulated, now connecting the whole tangle with the outside world.

The Acyclic Dependencies Principle is reflected by the Tangled metric, which is calculated as the ratio between the weight of the minimum feedback edges and the total weight of all edges in the graph. Thus, values greater zero indicate cyclic dependencies.

 
Next >
STAN 2.1.2

We are pleased to announce the 2.1.2 maintenance release of STAN, adding support for Java 8.

Read more...