Improve graph layout

[rgleichman]

Problem

Graphviz produces very spread out images when laying out medium to large functions. Please see this SVG image. findParentsWithEdges.zip

Background

There are a few causes for the large layout.

1. In the function doGraphLayout in app/Rendering.hs, the Graphviz node is set as a circle with a radius equal to the maximum height or width of the diagram. Since icon rotation happens after layout, using a large circle for the Graphviz node shape ensures that icons can be rotated without overlapping. However, this also means that the Graphviz node is much larger than the actual icon, especially for non-circular icons.
2. Graphviz does not seem to do a good job at graph layout when the node sizes have a high degree of variation. If Graphviz can not find a layout without overlaps, it reverts to scaling up the size of the layout. This means that all edges become longer.

Possible Solutions

1. Graphviz has many layout algorithms, and each algorithm has many parameters. It's possible a better choice of algorithm or parameters in app/Rendering.hs could improve things.
2. Something that might help would the following: after getting the graph layout from Graphviz, iteratively rotate the icons and check for overlap. Keep scaling down the layout until there is overlap. This approach might help a bit, but would not fix the deeper problem of a bad layout.
3. Create a better graph layout algorithm. Such an algorithm ideally would also incorporate node rotation with layout.

The current plan of action is to investigate solution #3, creating a better graph layout algorithm.

[flip111]

To avoid crossing edges planarization is needed. Efficiently packing shapes into a plane is a packing problem. You can also emply force to layout nodes, but this is an approximate solution, while exhaustive search on packing will give you the optimal solution (NP-complete problem though). A problem with a force directed graph is that you can not take the center point but have to calculate around the border of each node, which is a lot more calculations.

After laying out the nodes you need to make space between them to wire the edges, this is also non-trivial because the amount of edges routed between two nodes can vary and you might want to have more visually pleasing lines (like nice curve) rather than lines which are squeezed between nodes.

I think packing is a dead end because after planarization you want to rotate your subgraph in such a way that you get the minimal amount of edge length to the larger graph. After that you can determine how many edges are routed between nodes, this determines how much space you need between those nodes, you should adjust the force between a pair of nodes accordingly. To calculate force you can start with vertices on corners and for each pair of vertices you can calculate the nearest point on the border of the paired node.

The blue nodes suppose to represent a subgraph without crossing edges. I know that the orange nodes could be re-ordered so that they don't cross, but i think you get the point.

Here you see how you can calculate force by starting at vertices. Orange represents the closest vertex of the other node. In the second drawing you see how the black connections are discarded and force only applies to the closest nodes, this is useful if you don't want to rotate nodes for when you have written text. The green line represents the force between nodes, you have to calculate the point on the left node where the green line ends at the node boundary (at the right node it ends at a vertex so no extra calculation needed there). The last drawing calculates the optimal solution when it can take into account all pairing of vertices and thus is allowed to rotate the node.

By the way this is not a complete solutions because there are still enough problems to explore .. for example if you start with another rotation of the nodes then the edge will convert to each other differently. For a lot of problems you can also try some random combinations together with a measurement of how good they are (and possibly evolve from there if you want with a genetic algorithm or what not)

[rgleichman]

@flip111 Thank you for your detailed comment. These suggestions on how to get started approaching the problem are very helpful.

[flip111]

https://github.com/tgingold/ghdl/issues/111#issuecomment-344714406