Skip to content

use decomposition into biconnected components in Gomory-Hu tree #39478

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 1 commit into from
May 11, 2025
Merged

use decomposition into biconnected components in Gomory-Hu tree #39478

merged 1 commit into from
May 11, 2025

Conversation

dcoudert
Copy link
Contributor

@dcoudert dcoudert commented Feb 8, 2025

We use method blocks_and_cut_vertices to decompose the graph into biconnected components.

  • isolated vertices can be ignored
  • a block of size 2 is a cut-edge. It suffices to add an edge of capacity 1 to the tree.
  • it remains to compute the Gomory-Hu trees of the remaining biconnected components.

📝 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 self-assigned this Feb 8, 2025
@github-actions GitHub Actions
Copy link

github-actions bot commented Feb 8, 2025 •
edited
Loading

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

dcoudert added a commit to dcoudert/sage that referenced this pull request Feb 8, 2025
@dcoudert
sagemath#39478: take edge labels into account
4d140cf
dcoudert added a commit to dcoudert/sage that referenced this pull request Feb 8, 2025
@dcoudert
sagemath#39478: remove trailing whitespace
8956bf2
@dcoudert dcoudert force-pushed the graphs/use_biconnected_components_in_gomory_hu_tree branch from 9b08796 to 2cda7d5 Compare April 4, 2025 11:48
@dcoudert dcoudert requested a review from dimpase April 27, 2025 15:09
dimpase
dimpase approved these changes Apr 30, 2025
View reviewed changes
Copy link
Member

@dimpase dimpase left a comment

Choose a reason for hiding this comment

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

Is there a real need to "avoid" recursion by using a stack?

Anyway, LGTM

@dcoudert
Copy link
Contributor Author

Thank you for the review.

The stack has been introduced in #38791 to avoid reaching the maximum recursion depth (https://ask.sagemath.org/question/79577/graphs-gomory-hu-tree-memory-blow-up-and-max-recursion-depth/). Furthermore, the construction is faster this way.

vbraun pushed a commit to vbraun/sage that referenced this pull request May 1, 2025
76d912d 
sagemathgh-39478: use decomposition into biconnected components in Gomory-Hu tree
    
We use method `blocks_and_cut_vertices` to decompose the graph into
biconnected components.
- isolated vertices can be ignored
- a block of size 2 is a cut-edge. It suffices to add an edge of
capacity 1 to the tree.
- it remains to compute the Gomory-Hu trees of the remaining biconnected
components.

### 📝 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.
- [x] 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#39478
Reported by: David Coudert
Reviewer(s): Dima Pasechnik
vbraun pushed a commit to vbraun/sage that referenced this pull request May 4, 2025
b1ea279 
sagemathgh-39478: use decomposition into biconnected components in Gomory-Hu tree
    
We use method `blocks_and_cut_vertices` to decompose the graph into
biconnected components.
- isolated vertices can be ignored
- a block of size 2 is a cut-edge. It suffices to add an edge of
capacity 1 to the tree.
- it remains to compute the Gomory-Hu trees of the remaining biconnected
components.

### 📝 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.
- [x] 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#39478
Reported by: David Coudert
Reviewer(s): Dima Pasechnik
vbraun pushed a commit to vbraun/sage that referenced this pull request May 5, 2025
58f88dc 
sagemathgh-39478: use decomposition into biconnected components in Gomory-Hu tree
    
We use method `blocks_and_cut_vertices` to decompose the graph into
biconnected components.
- isolated vertices can be ignored
- a block of size 2 is a cut-edge. It suffices to add an edge of
capacity 1 to the tree.
- it remains to compute the Gomory-Hu trees of the remaining biconnected
components.

### 📝 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.
- [x] 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#39478
Reported by: David Coudert
Reviewer(s): Dima Pasechnik
vbraun pushed a commit to vbraun/sage that referenced this pull request May 6, 2025
b86e65c 
sagemathgh-39478: use decomposition into biconnected components in Gomory-Hu tree
    
We use method `blocks_and_cut_vertices` to decompose the graph into
biconnected components.
- isolated vertices can be ignored
- a block of size 2 is a cut-edge. It suffices to add an edge of
capacity 1 to the tree.
- it remains to compute the Gomory-Hu trees of the remaining biconnected
components.

### 📝 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.
- [x] 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#39478
Reported by: David Coudert
Reviewer(s): Dima Pasechnik
@vbraun vbraun merged commit 345329e into sagemath:develop May 11, 2025
26 checks passed
@darijgr darijgr mentioned this pull request Jul 27, 2025
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
1 more reviewer

@dimpase dimpase dimpase approved these changes

Reviewers whose approvals may not affect merge requirements
Assignees

@dcoudert dcoudert

Labels
c: graph theory
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@dcoudert @dimpase @vbraun