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. To view this discussion visit https://groups.google.com/d/msgid/sage-gsoc/7c6af4fa-5038-4e52-937e-804f465bdf3en%40googlegroups.com.
