Skip to content

Improve Feng, PNC algorithm #40510

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 6 commits into from
Aug 16, 2025
Merged

Improve Feng, PNC algorithm #40510

merged 6 commits into from
Aug 16, 2025

Conversation

kappybar
Copy link
Contributor

  • Fix several bugs of PNC algorithm.
  • Improve implementation of Feng algorithm.
  • Add PNC as a supported algorithm in shortest_simple_paths

📝 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

#40364

@dcoudert
Copy link
Contributor

Some failing doctests https://github.com/sagemath/sage/actions/runs/16621950853/job/47028268037?pr=40510#step:11:348

@dcoudert dcoudert added c: graph theory gsoc: 2025 Tag for GSoC2025 issues/PRs labels Jul 30, 2025
@dcoudert
Copy link
Contributor

dcoudert commented Aug 1, 2025

How difficult would it be to avoid the duplication of methods shortest_path_to_green and ancestor_idx_func ?

@kappybar
Copy link
Contributor Author

kappybar commented Aug 1, 2025

I think the easiest option is to integrates two functions and use common code except for while candidate_paths.size(): section. The current code is almost same, and can be exactly same.

The plan is to integrate feng_k_shortest_simple_paths, pnc_k_shortest_simple_paths into one function such as nc_k_shortest_simple_paths and add argument algorithm=(normal|postponed) to distinguish two algorithms.

@dcoudert
Copy link
Contributor

dcoudert commented Aug 1, 2025

I suggest to start with the "easy" parts that can be shared. I assume that mixing Feng and PNC is much more involved and prone to errors.

@kappybar
Copy link
Contributor Author

kappybar commented Aug 1, 2025

Now, L1103-L1236 is exactly same as L1401-L1534 in path_enumeartion.pyx.

def nc_k_shortest_simple_paths(self,...., algorithm="normal"):
     ...
     common codes for feng and pnc
     ...
     if algorithm == "normal":
           THE FENG ALGORITHM (L1237-L1287 in path_enumeration.pyx)
     elif algorithm == "postponed":
           THE PNC ALGORITHM  (L1535-L1597 in path_enumeration.pyx)

will keep two algorithms independent, so will not make serious error.

@kappybar
Copy link
Contributor Author

kappybar commented Aug 2, 2025

I am not sure how to handle deleted functions (e.g., Feng_k_shortest_simple_paths, pnc_k_shortest_simple_paths). Should I raise deprecated error in calling these functions?

dcoudert
dcoudert reviewed Aug 2, 2025
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.

An option is to keep both methods feng_k_shortest... and pnc_k_shortest... with only few tests and doing only yield from nc_k_shortest....
This way we avoid the need for deprecation.
Furthermore, it ease the manipulation of the different algorithms if one wants to do some benchmark.

src/sage/graphs/path_enumeration.pyx
@@ -571,11 +570,12 @@ def shortest_simple_paths(self, source, target, weight_function=None,
if not self.is_directed():
Copy link
Contributor

Choose a reason for hiding this comment

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

  1. this part can be simplified as follows
    if algorithm in ("Feng", '"PNC"):
        if not self.is_directed():
            raise ValueError(f"{algorithm}'s algorithm works only for directed graphs")

        yield from nc_k_shortest_simple_paths(self, source=source, target=target,
                                              weight_function=weight_function,
                                              by_weight=by_weight, check_weight=check_weight,
                                              report_edges=report_edges,
                                              labels=labels, report_weight=report_weight,
                                              postponed=algorithm == "PNC")

    elif algorithm == "Yen":
        yield from yen_k_shortest_simple_paths(self, source=source, target=target,
                                               weight_function=weight_function,
                                               by_weight=by_weight, check_weight=check_weight,
                                               report_edges=report_edges,
                                               labels=labels, report_weight=report_weight)
  1. instead of using parameter algorithm in nc_k_shortest_simple_paths, I propose to simply use a boolean postponed=True|False

src/sage/graphs/path_enumeration.pyx Outdated
# (i.e. real length = cost + shortest_path_length in T_0)
# this is used in the "postponed" algorithm
cdef priority_queue[pair[pair[double, bint], pair[int, int]]] candidate_paths2
if algorithm == "normal":
Copy link
Contributor

Choose a reason for hiding this comment

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

add an empty line before/after to improve readability.

src/sage/graphs/path_enumeration.pyx Outdated
new_cost = cost + deviation_weight
candidate_paths.push(((-new_cost, True), (new_path_idx, dev_idx)))
former_part.remove(path[deviation_i])
elif algorithm == "postponed":
Copy link
Contributor

Choose a reason for hiding this comment

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

add empty line before/after

@dcoudert
Copy link
Contributor

dcoudert commented Aug 2, 2025

you should update the branch on the last beta now that #40364 has been merged

@github-actions GitHub Actions
Copy link

github-actions bot commented Aug 2, 2025

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

dcoudert
dcoudert approved these changes Aug 3, 2025
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.

Further improvements are certainly possible, but it is enough for this PR.

@kappybar kappybar mentioned this pull request Aug 6, 2025
Merged
5 tasks
vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 10, 2025
cca04d1 
sagemathgh-40510: Improve Feng, PNC algorithm
    
<!-- ^ 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". -->

+ Fix several bugs of PNC algorithm.
+ Improve implementation of Feng algorithm.
+ Add PNC as a supported algorithm in shortest_simple_paths

### 📝 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.
- [ ] 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: ... -->
sagemath#40364
    
URL: sagemath#40510
Reported by: Yuta Inoue
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 10, 2025
a5f8082 
sagemathgh-40547: Update NC k shortest simple path for Undirected graphs
    
<!-- ^ 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". -->

Update nc_k_shortest_simple_path algorithm for undirected 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.
- [ ] 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: ... -->
sagemath#40510
    
URL: sagemath#40547
Reported by: Yuta Inoue
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 12, 2025
8e02188 
sagemathgh-40510: Improve Feng, PNC algorithm
    
<!-- ^ 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". -->

+ Fix several bugs of PNC algorithm.
+ Improve implementation of Feng algorithm.
+ Add PNC as a supported algorithm in shortest_simple_paths

### 📝 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.
- [ ] 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: ... -->
sagemath#40364
    
URL: sagemath#40510
Reported by: Yuta Inoue
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 12, 2025
441a4fc 
sagemathgh-40547: Update NC k shortest simple path for Undirected graphs
    
<!-- ^ 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". -->

Update nc_k_shortest_simple_path algorithm for undirected 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.
- [ ] 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: ... -->
sagemath#40510
    
URL: sagemath#40547
Reported by: Yuta Inoue
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 13, 2025
a7e130e 
sagemathgh-40510: Improve Feng, PNC algorithm
    
<!-- ^ 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". -->

+ Fix several bugs of PNC algorithm.
+ Improve implementation of Feng algorithm.
+ Add PNC as a supported algorithm in shortest_simple_paths

### 📝 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.
- [ ] 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: ... -->
sagemath#40364
    
URL: sagemath#40510
Reported by: Yuta Inoue
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 13, 2025
c8fd997 
sagemathgh-40547: Update NC k shortest simple path for Undirected graphs
    
<!-- ^ 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". -->

Update nc_k_shortest_simple_path algorithm for undirected 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.
- [ ] 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: ... -->
sagemath#40510
    
URL: sagemath#40547
Reported by: Yuta Inoue
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 14, 2025
8839d6c 
sagemathgh-40510: Improve Feng, PNC algorithm
    
<!-- ^ 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". -->

+ Fix several bugs of PNC algorithm.
+ Improve implementation of Feng algorithm.
+ Add PNC as a supported algorithm in shortest_simple_paths

### 📝 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.
- [ ] 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: ... -->
sagemath#40364
    
URL: sagemath#40510
Reported by: Yuta Inoue
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 14, 2025
b75fc79 
sagemathgh-40547: Update NC k shortest simple path for Undirected graphs
    
<!-- ^ 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". -->

Update nc_k_shortest_simple_path algorithm for undirected 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.
- [ ] 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: ... -->
sagemath#40510
    
URL: sagemath#40547
Reported by: Yuta Inoue
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 16, 2025
a17ac6b 
sagemathgh-40547: Update NC k shortest simple path for Undirected graphs
    
<!-- ^ 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". -->

Update nc_k_shortest_simple_path algorithm for undirected 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.
- [ ] 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: ... -->
sagemath#40510
    
URL: sagemath#40547
Reported by: Yuta Inoue
Reviewer(s): David Coudert
@vbraun vbraun merged commit c78cd54 into sagemath:develop Aug 16, 2025
23 of 25 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
1 more reviewer

@dcoudert dcoudert dcoudert approved these changes

Reviewers whose approvals may not affect merge requirements
Assignees
No one assigned
Labels
c: graph theory gsoc: 2025 Tag for GSoC2025 issues/PRs
Projects
None yet
Milestone
No milestone
Development

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