Identifying Dependencies for Breaking Cycles

Dependency cycles in software systems have very negative impact on characteristics like testability, understandability and reuse (as explained here). Cycles with only a few nodes (say 5 to 10) might be resolveable quite simply by manually analyzing them. For bigger cycles it is helpful to have an automated analysis at hand based on an algorithm solving the minimum feedback arc set problem. A feedback arc set of a directed graph is a subset of its arcs that upon removal would transform a cyclic into an acyclic directed graph. Such an algorithm combined with user input about the domain (i.e. which dependencies are absolutely necessary and which absolutely violate design decisions) is able to deliver excellent results.

Extending the Algorithm with User Input

There are a lot of algorithms that find a minimum weight set of arcs (i.e. the feedback arc set). Using such an algorithm, it quickly comes to mind that the algorithm itself does not have any knowledge about the problem domain. The feedback arc set is only based on the weight – the number of underlying parser dependencies in our case. That means even if a dependency has less weight it could be crucial to preserve it because it is compliant with the software design. On the other hand there might be dependencies that definitely should be removed because they clearly violate design decisions.

The obvious deduction is to instruct the algorithm with arcs having maximum weight (i.e. “please keep” – ignoring their real weight) and with arcs having minimum weight (i.e. “please remove” – ignoring their real weight). Clearly there are limitations. Instructing the algorithm in the mentioned way is only a hint. If no further candidates for removal exist even those the user would like to keep are removed.

Application in Practice

Sonargraph-Explorer uses an implementation of an algorithm that solves the feedback arc set problem adding the possibility to instruct it as explained above. For a cycle of 87 Java files the feedback arc set analysis result looks like this:

Based on weight and cycle participation, 2.77 % of the parser dependencies need to be removed in order to break the cycle completely. Once a developer specifies which dependencies should be kept and which removed the result will slightly change:

The algorithm determines a feedback arc set driven by domain aspects. An interesting information can also be seen in the highlighted line: By removing only 26 parser dependencies (0,96 % of the overall parser dependencies of the cyclic elements) the number of cyclic nodes can be brought down from 87 to 26, which would already be a big improvement.