GSoC Project: Paths and Cycles Enumeration in Graphs – Proposal & Intro
80 views
Skip to first unread message
Austin Jiang
Mar 31, 2025, 12:19:16 PMMar 31
to sage-gsoc
Hi SageMath GSoC Team,
I'm Austin from Canada, an incoming Computer Science undergraduate at the University of Cambridge.
I have a strong background in graph theory and algorithms, with extensive experience in competitive programming, graph-based problem modeling, and implementing algorithms such as Dijkstra, Bellman-Ford, Tarjan’s SCC, and various flow and matching techniques. I’ve also conducted research at Wolfram Research and contributed over 20 published functions to the Wolfram Function Repository.
I’m very excited about the GSoC project “Paths and Cycles Enumeration Methods in Graphs”, which aligns closely with my interests and experience. While initially exploring the k shortest simple paths problem, I considered using an A*-based approach. However, I later realized that due to its heuristic nature, the worst-case time complexity could be very bad in certain edge cases. After reading David's papers, “K-shortest simple paths using biobjective path search” and “Finding the k Shortest Simple Paths: Time and Space Trade-offs”, I was very inspired by their trade-off discussions. I’ve since decided to design the function with a flexible interface, allowing users to select the internal algorithm (e.g., "yen", "sb", "psb", "pnc", "nc") to better balance time and space complexity depending on the context.
In preparation for this project, I’m currently contributing to SageMath by submitting my first pull request on GitHub. This has helped me get familiar with the codebase and development workflow.
I’ve attached a draft of my proposal for this project and would greatly appreciate any feedback or suggestions you might have.
Looking forward to learning from and contributing to SageMath!
Best regards,
Austin Jiang
I'm Austin from Canada, an incoming Computer Science undergraduate at the University of Cambridge.
I have a strong background in graph theory and algorithms, with extensive experience in competitive programming, graph-based problem modeling, and implementing algorithms such as Dijkstra, Bellman-Ford, Tarjan’s SCC, and various flow and matching techniques. I’ve also conducted research at Wolfram Research and contributed over 20 published functions to the Wolfram Function Repository.
I’m very excited about the GSoC project “Paths and Cycles Enumeration Methods in Graphs”, which aligns closely with my interests and experience. While initially exploring the k shortest simple paths problem, I considered using an A*-based approach. However, I later realized that due to its heuristic nature, the worst-case time complexity could be very bad in certain edge cases. After reading David's papers, “K-shortest simple paths using biobjective path search” and “Finding the k Shortest Simple Paths: Time and Space Trade-offs”, I was very inspired by their trade-off discussions. I’ve since decided to design the function with a flexible interface, allowing users to select the internal algorithm (e.g., "yen", "sb", "psb", "pnc", "nc") to better balance time and space complexity depending on the context.
In preparation for this project, I’m currently contributing to SageMath by submitting my first pull request on GitHub. This has helped me get familiar with the codebase and development workflow.
I’ve attached a draft of my proposal for this project and would greatly appreciate any feedback or suggestions you might have.
Looking forward to learning from and contributing to SageMath!
Best regards,
Austin Jiang
Reply all
Reply to author
Forward
0 new messages