Skip to content

Graph constructors: Remove gratuitous nondeterminism #37942

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 3 commits into from
May 12, 2024
Merged

Graph constructors: Remove gratuitous nondeterminism #37942

merged 3 commits into from
May 12, 2024

Conversation

mkoeppe
Copy link
Contributor

@mkoeppe mkoeppe commented May 5, 2024

Since Python 3.x, dicts preserve insertion order.

Here we modify the processing of "dict-of-dicts" and "dist-of-lists" input formats to avoid going through set, which introduces gratuitous nondeterminism regarding the order of vertices.

This change gives for example this improvement:

sage: G = graphs.CubeGraph(3)
sage: G.vertices(sort=False)
['000', '001', '010', '011', '100', '101', '110', '111']

📝 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

dcoudert
dcoudert reviewed May 6, 2024
View reviewed changes
Copy link
Contributor

@dcoudert dcoudert left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM, but the build bot is failing. It should not be related, but..

@fchapoton
Copy link
Contributor

For a tentative to repair the currently very broken CI , see #37926

@dcoudert
Copy link
Contributor

dcoudert commented May 6, 2024

Some failing doctests due to this PR:

sage -t --long --warn-long 23.0 --random-seed=193680368306819097191129940761876851645 src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 15721, in sage.graphs.generic_graph.GenericGraph.cluster_triangles
Failed example:
    list(F.cluster_triangles().values())
Expected:
    [1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0]
Got:
    [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0]
**********************************************************************
sage -t --long --warn-long 23.0 --random-seed=193680368306819097191129940761876851645 src/sage/graphs/graph_decompositions/modular_decomposition.py
**********************************************************************
File "src/sage/graphs/graph_decompositions/modular_decomposition.py", line 372, in sage.graphs.graph_decompositions.modular_decomposition.print_md_tree
Failed example:
    print_md_tree(modular_decomposition(graphs.IcosahedralGraph()))
Expected:
    PRIME
     1
     5
     7
     8
     11
     0
     2
     6
     3
     9
     4
     10
Got:
    PRIME
     3
     4
     7
     9
     11
     1
     5
     8
     0
     2
     6
     10
**********************************************************************
File "src/sage/graphs/graph_decompositions/modular_decomposition.py", line 495, in sage.graphs.graph_decompositions.modular_decomposition.habib_maurer_algorithm
Failed example:
    print_md_tree(habib_maurer_algorithm(graphs.IcosahedralGraph()))
Expected:
    PRIME
     1
     5
     7
     8
     11
     0
     2
     6
     3
     9
     4
     10
Got:
    PRIME
     3
     4
     7
     9
     11
     1
     5
     8
     0
     2
     6
     10

@mkoeppe
Copy link
Contributor Author

mkoeppe commented May 6, 2024

Some failing doctests due to this PR:

Thanks.
I'll update these doctests after I've repaired the CI...

@github-actions GitHub Actions
Copy link

github-actions bot commented May 8, 2024

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

dcoudert
dcoudert approved these changes May 8, 2024
View reviewed changes
Copy link
Contributor

@dcoudert dcoudert left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented May 8, 2024

Thank you!

mantepse
mantepse reviewed May 8, 2024
View reviewed changes
src/sage/graphs/graph_input.py
@@ -504,7 +515,7 @@ def relabel(x):

is_directed = G.is_directed()
if not is_directed and multiedges:
v_to_id = {v: i for i, v in enumerate(verts)}
v_to_id = {v: i for i, v in enumerate(verts.keys())}
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

isn't enumerate(verts) precisely the same as enumerate(verts.keys())?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, that's right; I've written it in this verbose form for clarity only.

vbraun pushed a commit to vbraun/sage that referenced this pull request May 9, 2024
cc8ea2e 
sagemathgh-37942: Graph constructors: Remove gratuitous nondeterminism
    
<!-- ^ 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". -->

Since Python 3.x, `dict`s preserve insertion order.

Here we modify the processing of "dict-of-dicts" and "dist-of-lists"
input formats to avoid going through `set`, which introduces gratuitous
nondeterminism regarding the order of vertices.

This change gives for example this improvement:
```sage
sage: G = graphs.CubeGraph(3)
sage: G.vertices(sort=False)
['000', '001', '010', '011', '100', '101', '110', '111']
```

### 📝 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.
- [ ] 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#37942
Reported by: Matthias Köppe
Reviewer(s): David Coudert, Martin Rubey, Matthias Köppe
vbraun pushed a commit to vbraun/sage that referenced this pull request May 11, 2024
a7be5a2 
sagemathgh-37942: Graph constructors: Remove gratuitous nondeterminism
    
<!-- ^ 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". -->

Since Python 3.x, `dict`s preserve insertion order.

Here we modify the processing of "dict-of-dicts" and "dist-of-lists"
input formats to avoid going through `set`, which introduces gratuitous
nondeterminism regarding the order of vertices.

This change gives for example this improvement:
```sage
sage: G = graphs.CubeGraph(3)
sage: G.vertices(sort=False)
['000', '001', '010', '011', '100', '101', '110', '111']
```

### 📝 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.
- [ ] 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#37942
Reported by: Matthias Köppe
Reviewer(s): David Coudert, Martin Rubey, Matthias Köppe
vbraun pushed a commit to vbraun/sage that referenced this pull request May 12, 2024
da802dd 
sagemathgh-37942: Graph constructors: Remove gratuitous nondeterminism
    
<!-- ^ 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". -->

Since Python 3.x, `dict`s preserve insertion order.

Here we modify the processing of "dict-of-dicts" and "dist-of-lists"
input formats to avoid going through `set`, which introduces gratuitous
nondeterminism regarding the order of vertices.

This change gives for example this improvement:
```sage
sage: G = graphs.CubeGraph(3)
sage: G.vertices(sort=False)
['000', '001', '010', '011', '100', '101', '110', '111']
```

### 📝 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.
- [ ] 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#37942
Reported by: Matthias Köppe
Reviewer(s): David Coudert, Martin Rubey, Matthias Köppe
@vbraun vbraun merged commit 1162d82 into sagemath:develop May 12, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
2 more reviewers

@mantepse mantepse mantepse left review comments

@dcoudert dcoudert dcoudert approved these changes

Reviewers whose approvals may not affect merge requirements
Assignees

@mkoeppe mkoeppe

Labels
c: graph theory v: small
Projects
None yet
Milestone
sage-10.4
Development

Successfully merging this pull request may close these issues.
5 participants
@mkoeppe @fchapoton @dcoudert @mantepse @vbraun