Improve graph layout about glance HOT 3 OPEN

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)

from glance.

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

from glance.

ghdl/ghdl#111 (comment)

from glance.