Skip to content

wrong default algorithm for computing the diameter of weighted graphs #40013

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
Closed
2 tasks done
dcoudert opened this issue Apr 27, 2025 · 0 comments · Fixed by #40014
Closed
2 tasks done

wrong default algorithm for computing the diameter of weighted graphs #40013

dcoudert opened this issue Apr 27, 2025 · 0 comments · Fixed by #40014
Labels
c: graph theory t: bug

Comments

@dcoudert
Copy link
Contributor

Steps To Reproduce

sage: G = graphs.PetersenGraph()
sage: G.diameter(by_weight=True)

Expected Behavior

2.0

Actual Behavior

ValueError                                Traceback (most recent call last)
Cell In[2], line 1
----> 1 G.diameter(by_weight=True)

File ~/sage/src/sage/graphs/graph.py:5144, in Graph.diameter(self, by_weight, algorithm, weight_function, check_weight)
   5142 if algorithm in ['standard', '2sweep', 'multi-sweep', 'iFUB']:
   5143     if by_weight:
-> 5144         raise ValueError("algorithm '" + algorithm + "' does not work" +
   5145                          " on weighted graphs")
   5146     from sage.graphs.distances_all_pairs import diameter
   5147     return diameter(self, algorithm=algorithm)

ValueError: algorithm 'iFUB' does not work on weighted graphs

Additional Information

Algorithm 'iFUB' is currently only implemented for unweighted graphs.
The default algorithm should be 'DHV' for weighted graphs and 'iFUB' for unweighted graphs.

Environment

  • OS: all
  • Sage Version: 10.7.beta1

Checklist

  • I have searched the existing issues for a bug report that matches the one I want to file, without success.
  • I have read the documentation and troubleshoot guide
dcoudert added a commit to dcoudert/sage that referenced this issue Apr 27, 2025
@dcoudert
fix issue sagemath#40013
9111558
@dcoudert dcoudert mentioned this issue Apr 27, 2025
Merged
5 tasks
vbraun pushed a commit to vbraun/sage that referenced this issue Apr 30, 2025
sagemathgh-40014: set correct default algorithm for the diameter of (…
b3f52cf 
…un)weighted graphs

Fixes sagemath#40013.

We now ensure that the default algorithm is `'DHV'` for weighted graphs
and `'iFUB'` for unweighted graphs.

### 📝 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.
- [x] I have created tests covering the changes.
- [x] 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#40014
Reported by: David Coudert
Reviewer(s): Frédéric Chapoton
vbraun pushed a commit to vbraun/sage that referenced this issue May 1, 2025
027c96c 
sagemathgh-40014: set correct default algorithm for the diameter of (un)weighted graphs
    
Fixes sagemath#40013.

We now ensure that the default algorithm is `'DHV'` for weighted graphs
and `'iFUB'` for unweighted graphs.

### 📝 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.
- [x] I have created tests covering the changes.
- [x] 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#40014
Reported by: David Coudert
Reviewer(s): Frédéric Chapoton
vbraun pushed a commit to vbraun/sage that referenced this issue May 4, 2025
b1cf969 
sagemathgh-40014: set correct default algorithm for the diameter of (un)weighted graphs
    
Fixes sagemath#40013.

We now ensure that the default algorithm is `'DHV'` for weighted graphs
and `'iFUB'` for unweighted graphs.

### 📝 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.
- [x] I have created tests covering the changes.
- [x] 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#40014
Reported by: David Coudert
Reviewer(s): Frédéric Chapoton
vbraun pushed a commit to vbraun/sage that referenced this issue May 5, 2025
849d607 
sagemathgh-40014: set correct default algorithm for the diameter of (un)weighted graphs
    
Fixes sagemath#40013.

We now ensure that the default algorithm is `'DHV'` for weighted graphs
and `'iFUB'` for unweighted graphs.

### 📝 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.
- [x] I have created tests covering the changes.
- [x] 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#40014
Reported by: David Coudert
Reviewer(s): Frédéric Chapoton
vbraun pushed a commit to vbraun/sage that referenced this issue May 6, 2025
79a5d07 
sagemathgh-40014: set correct default algorithm for the diameter of (un)weighted graphs
    
Fixes sagemath#40013.

We now ensure that the default algorithm is `'DHV'` for weighted graphs
and `'iFUB'` for unweighted graphs.

### 📝 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.
- [x] I have created tests covering the changes.
- [x] 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#40014
Reported by: David Coudert
Reviewer(s): Frédéric Chapoton
vbraun pushed a commit to vbraun/sage that referenced this issue May 9, 2025
c9696b1 
sagemathgh-40014: set correct default algorithm for the diameter of (un)weighted graphs
    
Fixes sagemath#40013.

We now ensure that the default algorithm is `'DHV'` for weighted graphs
and `'iFUB'` for unweighted graphs.

### 📝 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.
- [x] I have created tests covering the changes.
- [x] 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#40014
Reported by: David Coudert
Reviewer(s): Frédéric Chapoton
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: graph theory t: bug
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

set correct default algorithm for the diameter of (un)weighted graphs dcoudert/sage
1 participant
@dcoudert