Fix issue 37587 regarding the Link class plot method

[soehms]

As suspected in https://github.com/sagemath/sage/issues/37587#issuecomment-2051141073 the issue can be fixed by adding the contraint for the exterior region.

In the differences of this branch just the lines below belong to the corresponding correction of the algorithm:

index 9d988d877c..33d0cae051 100644
--- a/src/sage/knots/link.py
+++ b/src/sage/knots/link.py
@@ -3607,36 +3607,55 @@ class Link(SageObject):
         # such that the resulting regions are in fact closed regions
         # with straight angles, and using the minimal number of bends.
         regions = sorted(self.regions(), key=len)
-        regions = regions[:-1]
         edges = list(set(flatten(pd_code)))
...
+            else:
+                # capacity of exterior region, only sink
+                capacity = len(r) + 4
...
         nregions = []
-        for r in regions:
+        for r in regions[:-1]:  # interior regions
             nregion = []

All other changes are intended to improve the readability of the code. To this end I change and introduce new variable names to make the origin of the ideas coming from the class OrthogonalLinkDiagram of Spherogram more explicit. Furthermore I make some codestyle fixes and change the sign of the capacity such that the sink appears to be positive and thus according to the usage in Spherogram and the literature cited there.

With this branch the knot reported in the issue is plotted like this:

sage: kn = Knots().from_dowker_code([30, 18, 20, 24, 22, 26, 28, 32, 2, 4, 6, 8, 12, 10, 16, 14])
sage: arcs = sorted(kn.arcs())
sage: cols = {tuple(arcs[i]): i for i in range(len(arcs))}
sage: kn.plot(color=cols)

New plot

To make comparison with other results more convenient I used different colours for the arcs. The corresponding result for PPL is this:

sage: kn.plot(color=cols, solver='PPL')

New plot with PPL

Without this branch the PPL version with colours has been this:

Old plot with PPL

The coloured wrong result has been this:

Old plot

Note, that this branch also changes other plot results in the documentation. For example:

Previously:

Old documentation

With this branch:

New documentation

:memo: Checklist

• [x] The title is concise and informative.
• [x] The description explains in detail what this PR is about.
• [x] I have linked a relevant issue or discussion.
• [ ] I have created tests covering the changes.
• [ ] I have updated the documentation and checked the documentation preview.

:hourglass: Dependencies

[github-actions[bot]]

Documentation preview for this PR (built with commit f117a9d65161328f382bc96306973b5fa8c99d3e; changes) is ready! :tada: This preview will update shortly after each push to this PR.

[miguelmarco]

Sorry for not seeing this before. I will try to review it in the next days.

As you mention, we first use integer programming to compute the number of bendings of the segments. I am surprised that a lack of checking the outer region has only caused problems in very few cases.

[miguelmarco]

Looks good.

As a side comment for the future, I think it would be worth considering an approach that is based on this.

[miguelmarco]

One minor comment though: I don't understand the rationale behind the "source" and "sink" naming that you use in the comments.

[soehms]

Looks good.

As a side comment for the future, I think it would be worth considering an approach that is based on this.

Sounds like a good idea!

[soehms]

One minor comment though: I don't understand the rationale behind the "source" and "sink" naming that you use in the comments.

I made another attempt in the current commit. I hope I have found a better wording for this.

[soehms]

Thanks for the review, @miguelmarco!