Algorithm for generating a software stack diagram

Answer 1

While not an algorithm (which is what you asked for) you might want to check out NDepend which performs similar analysis and generates similar diagrams to the one you're after:

http://ndepend.com/

(I have no affiliation with NDepend)

Answer 2

It's not always going to be possible to make such a diagram. The (acyclic) dependency relationship:

A depends on X, Y, Z

B depends on X, Y, Z

C depends on X, Y, Z

describes the complete bipartite graph on six vertices, which is non-planar. The consequence of this for the type of diagram you show is that at least one of the areas in your graph must be either split into two separate pieces, and/or at least one of the areas must not connect directly to its dependent.

This problem is avoided by graph-based visualisation (such as graphvis), where edges can cross each other.

The outline of a heuristic algorithm to produce the sort of diagrams you're looking for is as follows:

1. Parse the tree of dependencies to calculate a 'level' for each item. In the example I give above, X, Y and Z will each appear three times in this graph at level 1, as children of each of A, B and C (at level 0)
2. Draw the tree in the obvious way, with items at each 'level' at the same horizontal level, and their ancestors/children below/above them respectively. There is a choice as to what order the items are placed at each level.
3. Calculate some metric of how good the diagram is, based on how many times a single item is split into multiple areas on the graph. If the ordering of the items is good, and two or more areas representing the same item touch each other, you can fuse them together.
4. Use this metric to optimise the permutations of items at the same level, using a combinatorial optimisation algorithm such as the Metropolis algorithm.

This won't produce the best graph every time (if such a concept is even well-defined...) but should do a reasonable job for problems like your example.

Answer 3

STAN4J generates this kind of diagrams from java-code.