Layout orientation

[thchr]

The various layout algorithms usually do not have any preference with regard to the final "orientation" or "rotation" of the graph - on the other hand, it is often desirable to orient a graph layout to be primarily horizontal or vertical.

Arguably the simplest and cheapest approach^(*) for this would be to compute the dipole moment of a vertex layout (i.e., p = ∑_i (r_i - r_com) with center of mass r_com = ∑_i r_i and vertex positions r_i). Recentering to r_com and rotating by -θ = -tan⁻¹(p_y/p_x) of r_i then achieves alignment to e.g., the horizontal axis. This wouldn't work for symmetric graphs where p = 0 though.

Another option would be to compute the dipole moment based on edges rather than vertices, using p = ∑_⟨ij⟩ (r_i - r_j) with ⟨ij⟩ denoting edges.

The dipole approach is simple to implement, but it's not clear to me what a good interface for this would be: if desired, should it be a keyword argument to existing layouts or should it be possible to nest layouts (e.g., Align(Stress(...), ...))?

---

^(*) There's probably more sophisticated things that could be done. E.g., principle component analysis (PCA) would probably be better in case the layout has any significant "outlier" vertices. The principal axis would then correspond to the eigenvector associated with the largest eigenvalue of the covariance matrix C = ∑_i (r_i - r_com) (r_i - r_com)^T. This eigenvector could be computed by e.g., power iteration or the Lanczos method. The covariance matrix is 2×2 in 2D, so the eigendecomposition is cheap.
Aside from a better "global" view of the orientation of a layout, a benefit of a PCA approach is that it would treat symmetric graphs (zero dipole moment) properly. It's more expensive though - but maybeProbably worth it for generality.

[hexaeder]

I like the feature idea! As I just wrote in #80 , I think nested layouts might be a good idea. Its easy to implement and works with all layouts then. On the negative side, this means it is and will be always "opt in" and might be harder to discover. But maybe still a good tradeoff?