Problem
Sometimes, when the routing option nudgeSharedPathsWithCommonEndPoint is set to false, the nudgeOrthogonalRoutes() method of the ImproveOrthogonalRoutes class in libavoid makes the assertion
|
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:
|
// 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,
|
// 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:
|
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.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent