HOLA not trying all expansion options

[skieffer]

In #60, we improved the tree placement step in HOLA so that, instead of selecting a best placement and giving up if it proved infeasible, HOLA now backtracks and tries the next best placement. However, HOLA is still too eager to call a given placement infeasible in the first place.

In order to make a given tree placement, the target face needs to be expanded to make room for the tree box. This involves a call to Face::buildBestProjSeq(), but this method currently represents another step where HOLA is selecting a best option, trying it, and giving up without first trying the next best option.

To be precise, Face::buildBestProjSeq() must select one dimension, x or y, in which to expand first. It then attempts expansion in this order. If this fails, it currently gives up, but it should attempt expansion again, now handling the dimensions in the opposite order. This is because cases can arise in which expansion is impossible in one order, but possible in the other order.

Example

This example arises during HOLA layout of the graph Garr201001.tglf that I will include in a linked PR.
(Note that tree box 723 is rooted at node 195, with SW placement.)

We are now attempting to place a new tree box B rooted at node 192, with placement and growth directions both equal to NORTH. The width and height of B are roughly 3, resp. 2, times those of node 192.

Face::buildBestProjSeq() heuristically selects the x-dimension as the best one in which to expand first. When we attempt this, however, we generate a separation constraint that wants to put tree box 723 EAST of node 192, which is impossible, due to non-overlap constraints. We then give up, and call the tree placement impossible. In fact, as things stand, all 10 conceivable placements for this tree fail, and the entire layout fails.

Instead, Face::buildBestProjSeq() should now try expanding again, only now working in the y-dimension first.
When it tries this, it will generate a separation constraint that wants to put tree box 723 NORTH of node 192, which works.
This time the expansion succeeds, as does the tree placement, and the entire layout.