Skip to content

Conversation

soehms
Copy link
Member

@soehms soehms commented Apr 22, 2024

As suspected in #37587 (comment) 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

kn_new_cols

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

kn_new_cols_ppl

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

Old plot with PPL

kn_cols_ppl

The coloured wrong result has been this:

Old plot

kn_cols

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

Previously:

Old documentation

grafik

With this branch:

New documentation

grafik

📝 Checklist

  • The title is concise and informative.
  • The description explains in detail what this PR is about.
  • 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.

⌛ Dependencies

@soehms soehms added this to the sage-10.4 milestone Apr 22, 2024
Copy link

github-actions bot commented Apr 22, 2024

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

@soehms soehms marked this pull request as ready for review April 23, 2024 05:53
@soehms soehms requested review from tscrim and miguelmarco April 23, 2024 05:55
@miguelmarco
Copy link
Contributor

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
Copy link
Contributor

Looks good.

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

@miguelmarco
Copy link
Contributor

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

@soehms
Copy link
Member Author

soehms commented Apr 25, 2024

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
Copy link
Member Author

soehms commented Apr 25, 2024

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
Copy link
Member Author

soehms commented Apr 26, 2024

Thanks for the review, @miguelmarco!

vbraun pushed a commit to vbraun/sage that referenced this pull request Apr 28, 2024
sagemathgh-37851: Fix issue 37587 regarding the Link class plot method
    
<!-- ^ Please provide a concise and informative title. -->
<!-- ^ Don't put issue numbers in the title, do this in the PR
description below. -->
<!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method
to calculate 1 + 2". -->
<!-- v Describe your changes below in detail. -->
<!-- v Why is this change required? What problem does it solve? -->
<!-- v If this PR resolves an open issue, please link to it here. For
example, "Fixes sagemath#12345". -->

As suspected in
sagemath#37587 (comment)
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 9d988d8..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](https://githu
b.com/3-
manifolds/Spherogram/blob/3062478dd69a52a16e55b967dd46dfe940af9ea7/spher
ogram_src/links/orthogonal.py#L118) of
[Spherogram](https://github.com/3-manifolds/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

![kn_new_cols](https://github.com/sagemath/sage/assets/47305845/328ff242
-2a99-48b1-b55a-657f13db0fae)

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`

![kn_new_cols_ppl](https://github.com/sagemath/sage/assets/47305845/359b
2404-91a4-44bc-a949-5cc7dec9ba0f)


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

### Old plot with `PPL`

![kn_cols_ppl](https://github.com/sagemath/sage/assets/47305845/5bc9809c
-9aa5-4cb4-b700-7c833e5e598a)

The coloured wrong result has been this:

### Old plot

![kn_cols](https://github.com/sagemath/sage/assets/47305845/513651b5-
8aa7-4394-b5e1-0d6715e7fbe1)


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

Previously:

### Old documentation

![grafik](https://github.com/sagemath/sage/assets/47305845/41ef8ad9-
cbbd-42ed-a898-3cd565bab23e)


With this branch:

### New documentation

![grafik](https://github.com/sagemath/sage/assets/47305845/4bcff688-
10e6-4a79-9823-12205d58ac75)




### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [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.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#37851
Reported by: Sebastian Oehms
Reviewer(s):
@vbraun vbraun merged commit 969b687 into sagemath:develop May 2, 2024
@soehms soehms deleted the link_plot_37587 branch May 5, 2024 21:26
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants