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. > Le 27 mars 2025 à 15:31, Ziad Tarek <ziad20037...@gmail.com> a écrit : > > 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 > <mailto: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 > > <https://groups.google.com/d/msgid/sage-gsoc/b9c1c582-27c6-4518-a00f-37ec962473d8n%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/551BF2E2-FE91-480F-8B02-896F0403D412%40inria.fr.
