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 On Sunday, March 23, 2025 at 12:44:10 PM UTC+2 david....@inria.fr wrote: > 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. > > On Saturday, March 22, 2025 at 10:20:24 PM UTC+1 Ziad Tarek wrote: > >> 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 >> <https://github.com/sagemath/sage/pull/39754>). While working on this, I >> also discovered a bug and opened a corresponding issue (#39756 >> <https://github.com/sagemath/sage/issues/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! >> > -- 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/b9c1c582-27c6-4518-a00f-37ec962473d8n%40googlegroups.com.
