Skip to content
Vicky Vergara edited this page Mar 20, 2023 · 12 revisions

pgRouting's GSoC Ideas for 2023

This page is always a work in progress because we admit new ideas!

Table of Contents

pgRouting's GSoC Mentors:

Our mentors can mentor any project (unless otherwise stated).

Name 2023 Availability Mentor Years Other
Daniel Kastl 2009~2022 PSC
Vicky Vergara YES 2015~2022 PSC
Cayetano Benavent 2018~2020 PSC
Ashish Kumar YES 2022 GSoC-student 2020, 2021, PSC
Regina Obe YES 2021 PSC
Rajat Shinde YES - PSC
Shobhit Chaurasia YES - GSoC-student 2022

Introduction

So you are interested in becoming a Google Summer of Code student? This is great! but what should you do to improve your chances of being selected? We recommend reading

Remember to be proactive

  • Pick a bug or ask for one and work on fixing it so you learn the product and development environment
  • Discuss your ideas on the pgrouting-dev list
  • The best GSoC idea is YOUR idea! something that you are really interested in developing.

We like contributions on the pgRouting's products:

  • osm2pgrouting (C++ & SQL)
  • pgRouting (C & C++ & SQL)
  • vrpRouting (C & C++ & SQL)
  • pgroutingLayers for Qgis (python 3 & SQL)

Important

  • Number of projects to be accepted is based on mentor availability
  • Review the timeline (alternate link). This year you can spread your coding period over a period of 12 weeks to 22 weeks (June 13 - September 12 up to November 21), plan your proposal accordingly.
  • Regardless of the product, in order for the mentors to consider the proposal, the pgrouting application requirements must be finished and well documented inside the proposal.
    • Help for finishing these tasks will be provided by a mentor in pgrouting's gitter channel
    • It is not forbidden that you guide each other
    • It is forbidden to copy/paste from each other's proposal.
    • It is forbidden to copy/paste from a past year's proposal.
  • We would advise you to choose a different idea that is not chosen by some other student. If the idea is same, the exact algorithm should differ (e.g. choosing two different Boost Graph algorithms). So, please mention in the Gitter channel any idea that you are working upon, make sure that some other student is not simultaneously working on the same idea, to increase your chances to be selected.

Summary of Ideas

The projects are of multiple sizes, classified as medium (~175 hours) or large (~350 hours). Choose accordingly, based on your availability. Some projects can be classified in either of the categories, depending on the depth of implementation, so please mention in your proposal the timeline and the total hours.

Apart from the ideas mentioned below, you can choose any interesting ideas from the current issues (such as Functionality Request or Discussion), but please comment on the issue to know its current status and its relevance as a GSoC Idea. Not to mention, "small" bug fixes or feature addition don't comply with a complete GSoC project, but they can be worked upon anytime before the GSoC coding period to become more familiar with the pgRouting's codebase.

To give you an idea about possible pgRouting GSoC ideas that can be worked upon:

# Title Duration Description
1 pgr_KSP => pgr_yen 175 hours Rename and add Overloads
2 pgr_withPointsKSP => pgr_yen_withPoints 175 hours Rename and add Overloads
3 pgr_turnRestrictedPath -> pgr_Yen_trsp 175 hours Rename and add Overloads
4 pgr_drivingDistance -> pgr_dijkstraDD 175 hours Rename and Overloads
5 pgr_withPointsDD 175 hours Overloads

Other ideas? We are always interested in other ideas that potential students want to present. So please don't be shy, contact the pgrouting-dev mailing list and introduce yourself and your idea.

Completed in prior years

See a list of projects on pgRouting's Google Summer of Code site.

How to get started

If you're interested, you should introduce yourself and your project idea on the pgRouting Developer mailing list and pgrouting's gitter channel. Read our wiki pages for developers and debugging and ask for help if you get stuck.

pgRouting application requirements

Task 1: Intent of application

  • Open an issue on GSoC-pgRouting repository.
    Put the following Content inside the Issue:
- [ ] Intent of application 
- [ ] Code of Conduct reproduction
- [ ] Experience with GitHub & Git
- [ ] Build locally pgRouting
- [ ] Get familiar with C++
- [ ] Get familiar with pgRouting

# Intent of Application:
- [ ] Write a paragraph about yourself in a comment of this issue.
- [ ] Handwrite a copy the [code of conduct](https://github.com/pgRouting/pgrouting/blob/main/CODE_OF_CONDUCT.md)
  - [ ] Take a picture of copy and upload on a comment of this issue.

Task 2: Experience with GitHub & Git

Create a new issue on your fork with the following content:

- [ ] Fork the [GSoC-pgRouting](https://github.com/pgRouting/GSoC-pgRouting) repository
- [ ] activate issues in your fork
- [ ] open an issue in your fork and put this content on the issue
- [ ] Clone your fork repository in your computer
- [ ] Create remote named `upstream` pointing to https://github.com/pgRouting/GSoC-pgRouting
- [ ] checkout to the `develop` branch of `upstream`
- [ ] create new branch with name `<your-git-nick>-test`
- [ ] Edit `doc/src/pgRouting-introduction.rst` and put your name on contributor
- [ ] push the newly created branch with the change 
- [ ] Create a pull request to https://github.com/pgRouting/GSoC-pgRouting
- [ ] put link of the PR and of the issue on a comment on the issue you created on [GSoC-pgRouting](https://github.com/pgRouting/GSoC-pgRouting) repository

Note: The pull request will not be honored, it is just for testing your skills using Git/GitHub

Task 3: Build locally pgRouting

Create a new issue on your fork with the following content:

- [ ] Install requirements
  * Look in the documentation what are the requirements
- [ ] Copy/Paste in a comment of this issue the compilation
- [ ] Put the link of this issue on a comment of the issue of task 1

Task 4: Get familiar with C++

Create a new issue on your fork with the following content:

- [ ] https://www.youtube.com/watch?v=eidEEmGLQcU
  - [ ] Make Report
- [ ] https://www.youtube.com/watch?v=u5senBJUkPc
  - [ ] Make Report
- [ ] https://www.youtube.com/watch?v=YnWhqhNdYyk
  - [ ] Make Report
- [ ] https://www.youtube.com/watch?v=1OEu9C51K2A
  - [ ] Make Report
- [ ] https://www.youtube.com/watch?v=xnqTKD8uD64
  - [ ] Make Report
- [ ] https://www.youtube.com/watch?v=86xWVb4XIyE
  - [ ] Make Report
- [ ] Put the link of this issue on a comment of the issue of task 1

View the videos and make a:

  • one page
  • handwritten
    report of each one, Take a picture and add the picture of the report in a comment

Task 5: Get familiar with pgRouting

Create a new issue on your fork with the following content

- [ ] Follow the [workshop](https://workshop.pgrouting.org/dev/en/index.html)
- [ ] Workshop introduction
  - Do not use OSGeoLive. As a developer you should be able to follow the workshop with he installation done on task 3
  - [ ] Install other requirements
- [ ] Basic
  - [ ] [Prepare data](https://workshop.pgrouting.org/dev/en/basic/data.html)
    - [ ] Instead of `city_routing` use `<your-git-nick>-routing`
  - [ ] [Pedestrian Routing](https://workshop.pgrouting.org/dev/en/basic/pedestrian.html)
  - [ ] [Vehicle Routing](https://workshop.pgrouting.org/dev/en/basic/vehicle.html)
  - [ ] [SQL function](https://workshop.pgrouting.org/dev/en/basic/sql_function.html)
  - [ ] [pl/pgsql function](https://workshop.pgrouting.org/dev/en/basic/plpgsql_function.html)
- [ ] Make screenshots of your work, make sure that `<your-git-nick>-routing` is visible
- [ ] Put the link of this issue on a comment of the issue of task 1

Task 6: Add a section to your proposal

The section must contain the links to the 5 issues and to the pull request

Details of Ideas

Details of idea 1

Difficulty: Medium

  • pgr_KSP => pgr_yen
    • deprecate pgr_KSP
  • Have pgr_yen with all overloads:
    • one to one
    • one to many
    • many to one
    • many to many
    • combinations
  • Return columns on all overloads: seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
  • pgTap test equivalence with pgr_dijkstra when K = 1
  • Documentation of the new function
  • Documentation on how to migrate to the new function

Details of idea 2

Difficulty: Medium

  • pgr_withPointsKSP => pgr_yen_WithPoints
  • Have pgr_yen_WithPoints with all overloads:
    • one to one
    • one to many
    • many to one
    • many to many
    • combinations
  • driving_side CHAR: Value in [r,R,L,l] indicating if the driving side is:
    • r,R for right driving side
    • l,L for left driving side
    • Any other value (including NULL) will be considered as r
  • Return columns on all overloads: seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
  • pgTap test equivalence with pgr_withPoints when K = 1 and the points are actual vertices on the graph
  • Documentation of the new function
  • Documentation on how to migrate to the new function

Details of idea 3

Difficulty: Medium

  • pgr_turnRestrictedPath => pgr_Yen_trsp
  • Have pgr_Yen_trsp with all overloads:
    • one to one
    • one to many
    • many to one
    • many to many
    • combinations
  • Return columns on all overloads: seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
  • pgTap test equivalence with suitable function (when K = 1 and the points are actual vertices on the graph)
  • Documentation of the new function
  • Documentation on how to migrate to the new function

Details of idea 4

Difficulty: Medium

  • pgr_drivingDistance => pgr_dijkstraDD
  • Have pgr_dijkstraDD with all overloads:
    • single vertex
    • multiple vertices
  • Return columns on all overloads:
    • seq, depth, start_vid, node, edge, cost, agg_cost
    • See pgr_primDD
  • pgTap test equivalence with suitable function.
  • Documentation of the new function.
  • Documentation on how to migrate to the new function

Details of idea 5

Difficulty: Medium

  • Have pgr_withPointsDD with all overloads:
    • single vertex
    • multiple vertices
  • driving_side CHAR: Value in [r,R,L,l] indicating if the driving side is:
    • r,R for right driving side
    • l,L for left driving side
    • Any other value (including NULL) will be considered as r
  • Return columns on all overloads:
    • seq, depth, start_vid, node, edge, cost, agg_cost
    • See pgr_primDD & other DD functions including pgr_drivingDistance
  • pgTap test equivalence with suitable function
  • Documentation
  • Documentation on how to migrate to the new function
Clone this wiki locally