Skip to content

small cleanup in graphic_matroid#41649

Merged
vbraun merged 4 commits into
sagemath:developfrom
fchapoton:clean_graphic_matroid
Feb 25, 2026
Merged

small cleanup in graphic_matroid#41649
vbraun merged 4 commits into
sagemath:developfrom
fchapoton:clean_graphic_matroid

Conversation

@fchapoton

@fchapoton fchapoton commented Feb 15, 2026

Copy link
Copy Markdown
Contributor

just a very small-scale cleanup in the modified file

📝 Checklist

  • The title is concise and informative.
  • The description explains in detail what this PR is about.

@github-actions

github-actions Bot commented Feb 15, 2026 •
edited
Loading

Copy link
Copy Markdown

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

dcoudert
dcoudert reviewed Feb 15, 2026
View reviewed changes
Comment thread src/sage/matroids/graphic_matroid.pyx Outdated
dcoudert
dcoudert reviewed Feb 15, 2026
View reviewed changes
Comment thread src/sage/matroids/graphic_matroid.pyx Outdated

@dcoudert dcoudert Feb 15, 2026

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

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

variable vertex_list is no longer used in this method.

@fchapoton fchapoton Feb 15, 2026

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

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

en effet

gmou3
gmou3 reviewed Feb 15, 2026
View reviewed changes
Comment thread src/sage/matroids/graphic_matroid.pyx Outdated
Comment thread src/sage/matroids/graphic_matroid.pyx
dcoudert
dcoudert approved these changes Feb 15, 2026
View reviewed changes

@dcoudert dcoudert left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

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

LGTM.

other proposed changes can be done in a separate PR.

gmou3
gmou3 reviewed Feb 16, 2026
View reviewed changes
Comment thread src/sage/matroids/graphic_matroid.pyx
leaf_edges = [e for e in edge_set
if degree[e[0]] == 1 or degree[e[1]] == 1]
while leaf_edges:
for leaf in leaf_edges:

@gmou3 gmou3 Feb 16, 2026

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

Rename to leaf_edge.

Comment thread src/sage/matroids/graphic_matroid.pyx
degree[leaf[0]] -= 1
degree[leaf[1]] -= 1
leaf_edges = [e for e in edge_set
if degree[e[0]] == 1 or degree[e[1]] == 1]

@gmou3 gmou3 Feb 16, 2026

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

Just a note: this seems suboptimal.

@dcoudert dcoudert Feb 16, 2026

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

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

This problem can be solved in $O(n+m)$ time, where $n$ is the number of vertices and $m$ the number of edges. For that, we first need to associate edges to vertices (one set per vertex), and build the list of vertices with degree 1. Then, we take a vertex $u$ of degree 1, remove its incident edge from the list of $u$ and the list of its neighbor $v$, update the degree of $v$ and possibly add it to the list of vertices of degree 1. Repeat until the list is empty. The remaining edges form the cycle. This is the 2-core of the graph (this graph is 2-degenerate).

The current implementation has time complexity in $O(nm)$. That is, it will take a long time if the graph is a long chain attached to a cycle. However, I expect it to be fast enough in practice. It uses simple data structure and we may expect that the main loop on leaf_edges is repeated only a few times.

vbraun pushed a commit to vbraun/sage that referenced this pull request Feb 16, 2026
sagemathgh-41649: small cleanup in graphic_matroid
81ed666 
just a very small-scale cleanup in the modified file

### 📝 Checklist

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.

URL: sagemath#41649
Reported by: Frédéric Chapoton
Reviewer(s): David Coudert, Frédéric Chapoton, gmou3
gmou3 added a commit to gmou3/sage that referenced this pull request Feb 16, 2026
@gmou3
Collapse M = <def>; return M to return <def>
59ae0f4 
This follows the change in `graphic_matroid.pyx`:
sagemath#41649
@gmou3 gmou3 mentioned this pull request Feb 16, 2026
Merged
vbraun pushed a commit to vbraun/sage that referenced this pull request Feb 20, 2026
77d483a 
sagemathgh-41649: small cleanup in graphic_matroid
    
just a very small-scale cleanup in the modified file

### 📝 Checklist

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
    
URL: sagemath#41649
Reported by: Frédéric Chapoton
Reviewer(s): David Coudert, Frédéric Chapoton, gmou3
vbraun pushed a commit to vbraun/sage that referenced this pull request Feb 20, 2026
041e1c1 
sagemathgh-41651: refactor: collapse `M = <def>; return M` to `return <def>`
    
This follows the change in `graphic_matroid.pyx`:
sagemath#41649.
    
URL: sagemath#41651
Reported by: gmou3
Reviewer(s): David Coudert, Frédéric Chapoton
vbraun pushed a commit to vbraun/sage that referenced this pull request Feb 23, 2026
329c90e 
sagemathgh-41651: refactor: collapse `M = <def>; return M` to `return <def>`
    
This follows the change in `graphic_matroid.pyx`:
sagemath#41649.
    
URL: sagemath#41651
Reported by: gmou3
Reviewer(s): David Coudert, Frédéric Chapoton
@vbraun vbraun merged commit 14b6130 into sagemath:develop Feb 25, 2026
26 of 27 checks passed
@fchapoton fchapoton deleted the clean_graphic_matroid branch February 26, 2026 07:19
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@dcoudert dcoudert dcoudert approved these changes

+1 more reviewer

@gmou3 gmou3 gmou3 left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@fchapoton @dcoudert @gmou3 @vbraun