Improve PNC algorithm #40364

kappybar · 2025-07-02T13:33:41Z

Improve the implementation of PNC algorithm.
See comments in #40284.

📝 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

kappybar · 2025-07-02T14:18:35Z

I am wondering whether there can be more improvement of this implementation of PNC algorithm.

when getting a path in G \ path[:dev_idx] when path is not simple, I do not care green vertices (from green vertices, reachable to the target vertex by a path with residual weight 0, so shortest path is calculated effectively). To realize this, it will be better to implement dijkstra function tailoring to this case. (But I am not sure how the current shortest path function implemented. The current one may already be good. I will have to see the implementation.) I am not quite sure this improves the current implementation, but I think its worth trying. How do you think about it?

@dcoudert

github-actions · 2025-07-02T14:40:35Z

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

dcoudert · 2025-07-02T15:00:07Z

Some ideas to be tested:

instead of using shortest_paths from boost_graph, you could use G._backend.bidirectional_dijkstra_special. I don't know if it is faster, but at least it avoids to copy the graph to another format at each call.
Relabel the graph so that vertices are named from 0 to n-1. This way, instead of using a dictionary ancestor_idx_dict, you could use a list or C array or C++ vector. You will off course have to relabel a path before yielding it. To do so, you can use

cdef list int_to_vertex = list(G)
cdef dict vertex_to_int = {u: i for i, u in enumerate(int_to_vertex)}
G.relabel{perm=vertex_to_int, inplace=True)
cdef int id_source = vertex_to_int[source]
cdef int id_target = vertex_to_int[target]

The idea of modifying Dijkstra to stop when reaching a green vertex is interesting, but as you said, using the reduced weights should already speed up computation. So I'm not sure we of the benefit of yet another implementation of Dijkstra...

src/sage/graphs/path_enumeration.pyx

kappybar · 2025-07-09T12:36:14Z

I have done the second, the fourth improvements. It became slightly faster. I have already done the first one.
The remaining (possible) improvement is the thrid one. Now, I don't have time to implement yet another dijkstra, but I hope I can do it in a week and a few days.

dcoudert

the light be other possible improvements, but I'm not sure which ones yet.

src/sage/graphs/path_enumeration.pyx

dcoudert · 2025-07-11T08:40:47Z

Let me know if you plan to do more on this PR or if you prefer to use a follow up PR for other changes.

kappybar · 2025-07-12T12:31:58Z

Sorry for the inconvenience. I will plan to do more on this PR.

kappybar · 2025-07-13T12:41:38Z

I implemented the shortest path computation for a set of target vertices (not one target vertex) and use it to compute shortest path to green vertices in PNC algorithm. It became faster than previous one in my laptop (150-160ms to 90-100ms for graphs.Grid2dGraph(5, 5)).

dcoudert

a few suggestions to improve method shortest_path_to_set:

prefer source and targets to x and y_set
Ensure that exclude_vertices is turned to a set when not empty to speed up tests
add tests for cases when the source is in exclude_vertices or in targets
is the method working well if a target is in exclude_vertices ?
is it faster to use a priority queue or a pairing heap (this data structure has decrease key operation) ?
when iterating over edges, prefer label to l to avoid confusion with 1

kappybar · 2025-07-14T13:12:12Z

is it faster to use a priority queue or a pairing heap (this data structure has decrease key operation)

They are not much different. Either one is ok.

dcoudert · 2025-07-14T13:23:23Z

you should rebase on the last beta to better highlight the changes done in this PR.

…on in pnc algorithm)

dcoudert

Shouldn't we raise an error when no path can be found ?

…path_to_set

dcoudert · 2025-07-16T14:04:15Z

I agree with the addition of the shortest path to set method. This might be useful to others.
However, the drawback for our case is the need for extracting the set of green vertices. The advantage of coloring vertices is to explore a smaller portion of the graph when calling Dijkstra. It may happen that the identification of the set of green vertices dominates the search.
An alternative is to design a specific shortest path method that calls ancestor_idx_func, and so colors the smallest possible portion of the graph. There is a tradeoff to find here.

kappybar · 2025-07-17T00:53:13Z

I agree with you. Coloring only necessary portions of graphs will be faster. I try to implement it.

dcoudert

is it faster in your experiments ?

src/sage/graphs/path_enumeration.pyx

kappybar · 2025-07-17T13:15:52Z

is it faster in your experiments ?

It is a little faster, though I tested only one instance.

D = graphs.Grid2dGraph(5, 5).relabel(inplace=False).to_directed()
%time len(list(pnc(D, 0, 24)))

will take about 90ms now, but previous one takes about 110ms. And execution time becomes stable (the previous one sometimes takes 150ms), but I don't know why.

I would like to also know how execution time changed in your environment.

dcoudert · 2025-07-17T15:17:18Z

on a linux computer I get

sage: D = graphs.Grid2dGraph(5, 5).relabel(inplace=False).to_directed()
sage: %time len(list(pnc(D, 0, 24)))
CPU times: user 159 ms, sys: 6 µs, total: 159 ms
Wall time: 159 ms
8512

on a Mac M1 I get

sage: %time len(list(pnc(D, 0, 24)))
CPU times: user 232 ms, sys: 1.02 ms, total: 233 ms
Wall time: 232 ms
8512

both are faster than what I get before.

kappybar · 2025-07-22T12:14:22Z

@dcoudert
I think this implementation of PNC algorithm became faster than before.
Is it ok to finish this PR?

dcoudert

I agree that it's faster than before. Thanks.

LGTM.

sagemathgh-40364: Improve PNC algorithm       Improve the implementation of PNC algorithm. See comments in sagemath#40284. ### 📝 Checklist  - [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    sagemath#40284 URL: sagemath#40364 Reported by: Yuta Inoue Reviewer(s): David Coudert

sagemathgh-40510: Improve Feng, PNC algorithm       + Fix several bugs of PNC algorithm. + Improve implementation of Feng algorithm. + Add PNC as a supported algorithm in shortest_simple_paths ### 📝 Checklist  - [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    sagemath#40364 URL: sagemath#40510 Reported by: Yuta Inoue Reviewer(s): David Coudert

github-actions bot added the s: needs review label Jul 2, 2025

dcoudert added c: graph theory gsoc: 2025 Tag for GSoC2025 issues/PRs labels Jul 2, 2025

dcoudert reviewed Jul 2, 2025

View reviewed changes

src/sage/graphs/path_enumeration.pyx Outdated Show resolved Hide resolved

dcoudert reviewed Jul 9, 2025

View reviewed changes

src/sage/graphs/path_enumeration.pyx Outdated Show resolved Hide resolved

src/sage/graphs/path_enumeration.pyx Outdated Show resolved Hide resolved

dcoudert reviewed Jul 14, 2025

View reviewed changes

kappybar added 8 commits July 14, 2025 22:40

improve pnc algorithm

0760376

remove unnecessary calculation of non-simple path

a84f579

replace list with set

511ef38

relabel vertices to numbers to improve

4ae3801

fix

d84959b

implement shortest_path_to_set (for efficient shortest path computati…

2a848ff

…on in pnc algorithm)

fix and add tests of shortest_path_to_set

9b7b880

change priority queue into paring heap in shortest_path_to_set

47e3d3a

kappybar force-pushed the improve_pnc branch from 565196c to 47e3d3a Compare July 14, 2025 13:52

kappybar added 2 commits July 14, 2025 22:55

erase unnecessary import

861ce00

erase unnecessary import

bf2487a

dcoudert reviewed Jul 15, 2025

View reviewed changes

raise an error when no path found from source to targets in shortest_…

b688c68

…path_to_set

kappybar added 2 commits July 17, 2025 21:49

change to get green vertices adaptively

72d5908

change function name

4628742

dcoudert reviewed Jul 17, 2025

View reviewed changes

src/sage/graphs/path_enumeration.pyx Outdated Show resolved Hide resolved

mino fix

3f1ddc6

dcoudert approved these changes Jul 22, 2025

View reviewed changes

dcoudert added s: positive review and removed s: needs review labels Jul 22, 2025

kappybar mentioned this pull request Jul 30, 2025

Improve Feng, PNC algorithm #40510

Merged

5 tasks

vbraun merged commit b9cbfdd into sagemath:develop Aug 2, 2025
22 of 24 checks passed

github-actions bot removed the s: positive review label Aug 2, 2025

Uh oh!

Improve PNC algorithm #40364

Improve PNC algorithm #40364

Uh oh!

Conversation

kappybar commented Jul 2, 2025

📝 Checklist

⌛ Dependencies

Uh oh!

kappybar commented Jul 2, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions bot commented Jul 2, 2025

Uh oh!

dcoudert commented Jul 2, 2025

Uh oh!

Uh oh!

kappybar commented Jul 9, 2025

Uh oh!

dcoudert left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

dcoudert commented Jul 11, 2025

Uh oh!

kappybar commented Jul 12, 2025

Uh oh!

kappybar commented Jul 13, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dcoudert left a comment

Choose a reason for hiding this comment

Uh oh!

kappybar commented Jul 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dcoudert commented Jul 14, 2025

Uh oh!

dcoudert left a comment

Choose a reason for hiding this comment

Uh oh!

dcoudert commented Jul 16, 2025

Uh oh!

kappybar commented Jul 17, 2025

Uh oh!

dcoudert left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

kappybar commented Jul 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dcoudert commented Jul 17, 2025

Uh oh!

kappybar commented Jul 22, 2025

Uh oh!

dcoudert left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

kappybar commented Jul 2, 2025 •

edited

Loading

kappybar commented Jul 13, 2025 •

edited

Loading

kappybar commented Jul 14, 2025 •

edited

Loading

kappybar commented Jul 17, 2025 •

edited

Loading