libavoid: false assertion in nudgeOrthogonalRoutes() when nudgeSharedPathsWithCommonEndPoint is false

[skieffer]

Problem

Sometimes, when the routing option nudgeSharedPathsWithCommonEndPoint is set to false, the nudgeOrthogonalRoutes() method of the ImproveOrthogonalRoutes class in libavoid makes the assertion

adaptagrams/cola/libavoid/orthogonal.cpp

Line 2925 in dd09dad

COLA_ASSERT(vs[i - 1]->id == channelLeftID);

which turns out to be false, and the process crashes.

Review

As a non-author of libavoid, I want to start with a review of how orthogonal connector
nudging works, for the sake of my own understanding as much as anyone else's.

The nudgeOrthogonalRoutes() function works one dimension at a time, and I will
assume throughout that we are working in the y-dimension. This means we are looking at
all of the horizontal connector segments, and we are interested in adjusting their y-coords,
in order to nudge them apart.

Before nudging can begin, each segment is assigned a channel.
The channel for a given horizontal segment is a rectangle whose x-interval equals that of the segment,
and whose y-interval is defined by the min and max allowed y-coords for this segment. These
bounds are defined by the set of all obstacles. The channel thus represents the space
in which the segment is allowed to move up or down in the nudging process. Importantly, either of the
upper or lower bounds may be infinite, in cases where there are no obstacles in the way.

The basic process of nudgeOrthogonalRoutes() is to partition the set of all horizontal segments into
groups whose channels overlap, and then to work one group at a time.
For each group, nudgeOrthogonalRoutes() sets up a vpsc problem, to try to nudge
the segments apart by the desired nudging distance. If the vpsc problem is not satisifed,
it decreases the nudging distance and tries again. It tries at most 10 times, then gives up on that group,
leaving all segments in their original position.

justUnifying

The nudgeOrthogonalRoutes() is actually called twice in the overall routing process, the first time with
a flag, justUnifying = true, which makes it conduct a very different process, explained by the comment here:

adaptagrams/cola/libavoid/orthogonal.cpp

Lines 2547 to 2551 in dd09dad

	// Do Unifying first, by itself. This greedily tries to position free
	// segments in overlapping channels at the same position. This way they
	// have correct nudging orders determined for them since they will form
	// shared paths, rather than segments just positioned as an results of
	// the routing process. Of course, don't do this when rerouting with

The vpsc problem

A vpsc problem is defined by a set of variables and a set of constraints. For each group of segments,
we set up the following problem.

Variables

What are the variables in a nudging problem?
They are of four kinds:

• Free: represents a connector segment that is allowed to wind up anywhere within its channel
• Fixed: represents a connector segment that is required to stay in its starting position
• Left Channel: represents the "left" side of a channel (the upper side, when working in the y-dimension)
• Right Channel: represents the "right" side of a channel (the lower side, when working in the y-dimension)

Constraints

What are the constraints?

• Free vars must stay between their corrsp. left and right channel vars
• Separation constraints to achieve the desired nudging
• Certain equality constraints for special cases defined here

The special case equality constraints -- the third item above -- play a critical role in the issue discussed here.

Weights

The vpsc problem defined in nudgeOrthogonalRoutes() takes a "soft" approach to the variables that are not supposed
to move, which includes all three of the fixed, left, and right variables. Instead of strictly forbidding movement,
with the possibility that vpsc could actually fail, it uses weights. It puts a weight of 100000 on the variables that
should not move, and a weight of 0.001 on the free variables. This means the vpsc problem is always solvable. After it
is solved, nudgeOrthogonalRoutes() assesses whether it was satisfied or not, by checking whether any of the heavy-weight
variables was moved from its desired position by more than a small threshold value (0.0001).

Responding to an unsatisfied vpsc problem

The issue arises in the way nudgeOrthogonalRoutes() responds to an unsatisfied vpsc problem, i.e. one in which one or more
fixed vars was forced to move.

The goal is to determine the set of separation constraints whose gaps should be diminished before trying again.
For this, nudgeOrthogonalRoutes() uses a notion of an "unsat range," a closed interval of indices into the vector of vpsc variables, being those fixed variables that were forced to move.

It is in the process of determining these ranges that the false assertion is made. The expectation expressed here,

adaptagrams/cola/libavoid/orthogonal.cpp

Lines 2918 to 2925 in dd09dad

	// There are no existing unsatisfied ranges,
	// so start a new unsatisfied range.
	// We are looking at a unsatisfied right side
	// where the left side was satisfied, so the
	// range begins at the previous variable
	// which should be a left channel side.
	COLA_ASSERT(i > 0);
	COLA_ASSERT(vs[i - 1]->id == channelLeftID);

implies that, if a right channel side had to move, this channel must also have a left side. But this is not always true, as the following example will show. When the corresponding left channel var is absent, the second assertion above fails.

Example

The example routing problem we'll look at succeeds if the routing option nudgeSharedPathsWithCommonEndPoint is true;
it fails with the false assertion when this option is false. In order to be able to visualize and understand the routing problem,
we begin by looking at the successful routing we get when nudgeSharedPathsWithCommonEndPoint is true:

By commenting out the problematic assertions, and setting nudgeSharedPathsWithCommonEndPoint back to false, we can see how the routing looks before the nudging attempt:

In the "no-nudging" image, I have labeled the four different desired y-coords that come up in the vpsc problem (see below), which concerns the segments in the group at the top of the diagram.

In the "with-nudging" image, it is easy to see all the different connectors that were bundled together at these y-coords, before nudging.

Problematic vars and constraints

The vpsc problem constructed for the segments participating in this group has 13 variables, and 23 constraints.

Variables

index, id, desiredPosition, finalPosition, weight,   notes

0,      0,  -516.954,       -503.733,       0.001    ConnRef 49
1,      3,  -516.954,       -503.733,       100000     UNSAT

2,      0,  -516.954,       -507.733,       0.001    ConnRef 27
3,      3,  -516.954,       -507.733,       100000     UNSAT


4,      1,  -485.291,       -507.733,       100000     UNSAT   ConnRef 35


5,      0,  -458.302,       -503.733,       0.001
6,      3,  -458.302,       -458.302,       100000

7,      0,  -458.302,       -507.733,       0.001    ConnRef 48
8,      3,  -458.302,       -458.302,       100000

9,      0,  -458.302,       -507.733,       0.001    ConnRef 41
10,     3,  -458.302,       -458.302,       100000


11,     0,  -431.639,       -507.733,       0.001
12,     3,  -431.639,       -431.639,       100000

Note: the id column indicates which of the four types each variable is:

free=0, fixed=1, left=2, right=3

Notice that there are no left variables in this problem. This simply reflects the fact that, for all of these segments, there is no lower channel boundary, because we are at the top of the diagram. There are no obstacles above, and these segments are allowed to move up as far as they want.

The three unsatisfied vars (1, 3, and 4) are noted in the notes column.

Constraints

I will not spell out all 23 constraints. I believe that most of them are fine, while the problematic ones are the following equality constraints:

v7 == v2
v7 == v4

v9 == v2
v9 == v4
v9 == v7

v11 == v2
v11 == v4
v11 == v7
v11 == v9

Each of these is one of the special case equality constraints noted earlier, and is generated here:

adaptagrams/cola/libavoid/orthogonal.cpp

Lines 2796 to 2808 in dd09dad

	else if (!nudgeSharedPathsWithCommonEnd &&
	(m_shared_path_connectors_with_common_endpoints.count(
	UnsignedPair(currSegment->connRef->id(), prevSeg->connRef->id())) > 0))
	{
	// We don't want to nudge apart these two segments
	// since they are from a shared path with a common
	// endpoint. There might be multiple chains of
	// segments that don't all have the same endpoints
	// so we need to make this an equality to prevent
	// some of them possibly getting nudged apart.
	thisSepDist = 0;
	equality = true;
	}

Simplifying all these constraints, they amount to:

v2 == v4 == v7 == v9 == v11

Since v4 is supposed to be fixed, while v2 <= v3 and v3 is fixed at a position less than v4, the problem is unsatisfiable.

Because the problem is unsatifiable, and in particular because the right channel vars v1 and v3 are forced to move, the
nudgeOrthogonalRoutes() function asserts that these right channel vars have corresponding left channel vars. But they do not.

The assertion seems reasonable. It is reasonable to expect that, when a channel boundary is forced to move, it is because the channel is too narrow, there is not enough space for the free vars inside. And that requires that both sides of the channel are finite. But the present example shows a case where channel boundaries are forced to move for a very different reason, namely the special equality constraints generated in the if (!nudgeSharedPathsWithCommonEnd... clause.

Possible solution

In the example, it seems to me that the equality constraints are inappropriate unless the segments' desired positions are equal. So, v9 == v7 may make sense, but each of v2, v4, v11 should be allowed to differ, since they all have different desired positions.

In terms of the comments written in the code where these equality constraints are generated, it seems like we shouldn't be trying to "prevent" these segments from being "nudged apart." They already are apart, and we want them that way.

I wonder if these equality constraints were only really meant to keep together those segments that were put together during the justUnifying pass.

Should this be added as another condition? If so, the clause:

else if (!nudgeSharedPathsWithCommonEnd &&
        (m_shared_path_connectors_with_common_endpoints.count(
             UnsignedPair(currSegment->connRef->id(), prevSeg->connRef->id())) > 0))

would become:

else if (!nudgeSharedPathsWithCommonEnd &&
        (m_shared_path_connectors_with_common_endpoints.count(
             UnsignedPair(currSegment->connRef->id(), prevSeg->connRef->id())) > 0) &&
             currSegment->variable->desiredPosition == prevSeg->variable->desiredPosition)

To really judge whether this is the right solution would require a full grasp of all the cases these
equality constraints were designed to handle, and I don't have that grasp. I will open a PR to encode
this solution, as well as to provide the test case that generated the figures above, but I will mark
it as a draft, since I'm not sure if it's really the right solution or not.

[skieffer]

The proposed solution does produce a nice result:

It is kind of a middle ground between the two figures in the original post. There is some nudging, while still honoring the
nudgeSharedPathsWithCommonEnd = false setting.