Interest in Paths and Cycle Enumeration Project and a Possible Approach

[Soham Rane]

Hello everyone!
My name is Soham Rane, and I am a sophomore at VJTI Mumbai with a strong background in competitive programming. You can find my Codeforces handle here: bingo. I am very interested in contributing to the "Paths and Cycle Enumeration" project and would love to share my approach with you.

I have recently contributed to SageMath (for automating changelog generation), which has given me some familiarity with the codebase. I am excited to dive deeper and contribute to the core SageMath project.

I’ve reviewed the project description, especially regarding the enumeration of simple cycles in undirected graphs, and these were my initial thoughts.

The current all_simple_cycles method for directed graphs seems to use an algorithm similar to Johnson’s algorithm, starting with finding strongly connected components (SCCs). However, this approach doesn’t apply directly to undirected graphs, as SCCs are not valid in this context.

For undirected graphs, I propose using Paton's algorithm, which is suitable for cycle enumeration in undirected graphs. To extend this to the enumeration of cycles by increasing weight, I suggest modifying Paton's algorithm by first sorting the fundamental cycles found in the initial step. Once sorted, we can consider combinations of these fundamental cycles, enumerating them in increasing weight to find next shortest cycle.

Regarding the "k shortest simple paths" problem, I am exploring algorithms like Yen’s algorithm and Eppstein’s algorithm.

I’d appreciate any suggestions or guidance on how best to approach this problem and any recommendations you may have

Best regards,
Soham Rane

[David Coudert]

Thank you for your interest in this project.

Your ideas for the enumeration of paths in undirected graphs are interesting.

An alternative to consider is also to simply make an interface with the method used in networkx if it is efficient.

To get the current state of implementation, you can look at the code of the graph module.

You will find methods for the enumeration of simple paths, the k shortest simple paths, cycles, etc.

For more advanced algorithms for the k shortest simple path, you can read recent papers

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

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

Note that Eppstein’s algorithm may enumerate non simple paths.

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/7c6af4fa-5038-4e52-937e-804f465bdf3en%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/