Paths and Cycles Enumeration Methods in Graphs – GSoC 2025

[Ziad Tarek]

Hello everyone,

I hope you are doing well.

My name is Ziad, and I am interested in the Paths and Cycles Enumeration Methods in Graphs project for GSOC 2025.

I have successfully built Sage from the source code and have started working on some issues (PR #39754). While working on this, I also discovered a bug and opened a corresponding issue (#39756), and I am currently working on a solution.

I am actively familiarizing myself with the SageMath source code and hope to contribute more. I find the project fascinating and would appreciate any guidance you could provide to help me prepare better for GSOC.

Thank you for your time!

[David....@inria.fr]

Thank you for your interest in this project and your first contributions to Sagemath.

Recall that the short description gives ideas for the project and you, the potential contributor, are expected to turn the ideas into a full proposal.

For algorithms, you can read for instance recent papers on the k shortest simple paths like

- https://dl.acm.org/doi/pdf/10.1145/3626567  and references there in

- https://link.springer.com/article/10.1007/s12532-025-00276-0 

Sincerely,

David.

[Rishav Ray Chaudhury]

Hey David, I am interested in contributing too. But my message got deleted when I posted it. Did I break any rule of the group? Sorry for saying this in this thread.

[tcscrims]

Hey David, I am interested in contributing too. But my message got deleted when I posted it. Did I break any rule of the group? Sorry for saying this in this thread.

No. It might have been accidentally flagged as a double post.

Best,

Travis 

[Ziad Tarek]

Hello David,

Thank you for your response.

Enumeration of Simple Cycles:
I reviewed the already implemented all_simple_cycles for directed graphs. I see that it uses a concept similar to Johnson's algorithm by obtaining strongly connected components (SCCs) and then using a BFS to enumerate cycles starting at the same vertex, along with a heap to store cycles from different starting vertices. This ensures that the shortest cycles are yielded first.

I believe we can extend this approach to support either undirected graphs or weighted graphs. For undirected graphs, we can use biconnected components to achieve a similar division as SCCs in directed graphs. For weighted graphs, instead of using a BFS, we can adopt a Dijkstra-like method by storing the cycle weight and sorting on it, which ensures that cycles with smaller weights are extracted first.

I also saw the suggestion of making an interface to networkX implemented method, but the current method does not support weighted graphs. I am still searching for more recent and efficient solutions for enumerating cycles in increasing order of weight.

K Shortest Simple Paths:
I have read the attached paper and reviewed the current implemented methods. I saw that two currently implemented algorithms are Yen’s algorithm and the Feng (node classification). The shortest_simple_paths method uses Yen’s algorithm for undirected graphs and Feng’s for directed graphs.

What I propose is implementing PNC (Postponed Node-Classification) and PSB (Parsimonious Sidetracks-Based) methods and deciding which to use based on certain thresholds (perhaps the average degree of nodes and the graph diameter) and some analysis to determine which is optimal, such as when the graph resembles a complex network.

These are the current approaches I am considering. Any feedback or suggestions would be greatly appreciated.

I am currently drafting a proposal. Would you be able to look over my proposal and provide feedback, and if so where should I send it?

Best regards,
Ziad

[David Coudert]

Hello,

I think that your ideas are good.

Note that I will unfortunately not have time to help proof reading proposals (currently involved in several committees).

Sincerely,

David.

--
You received this message because you are subscribed to the Google Groups "sage-gsoc" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-gsoc+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/sage-gsoc/b9c1c582-27c6-4518-a00f-37ec962473d8n%40googlegroups.com.

——
David Coudert
Equipe-Projet COATI
Centre Inria d’Université Côte d'Azur
Université Côte d’Azur, Inria, CNRS, I3S, France
http://www-sop.inria.fr/members/David.Coudert/