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. > Le 7 mars 2025 à 18:29, Soham Rane <sohamrane...@gmail.com> a écrit : > > 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 <https://codeforces.com/profile/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 > > -- > 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+unsubscr...@googlegroups.com > <mailto:sage-gsoc+unsubscr...@googlegroups.com>. > To view this discussion visit > https://groups.google.com/d/msgid/sage-gsoc/7c6af4fa-5038-4e52-937e-804f465bdf3en%40googlegroups.com > > <https://groups.google.com/d/msgid/sage-gsoc/7c6af4fa-5038-4e52-937e-804f465bdf3en%40googlegroups.com?utm_medium=email&utm_source=footer>. —— 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/ -- 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+unsubscr...@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/sage-gsoc/8338A8C0-5287-4A61-812F-E308353B133C%40inria.fr.
