GSoC Ideas: 2024 - pgRouting/pgrouting GitHub Wiki

pgRouting's GSoC Ideas for 2024

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 2024 Availability Mentor Years Other
Vicky Vergara YES 2015~2023 PSC
Regina Obe YES 2021~2023 PSC
Ashish Kumar YES 2022~2023 GSoC-student 2020, 2021, PSC
Rahul Chauhan YES 2020~2023 GSoC-student 2017, 2018
Jose Rios YES PgRouting Contributor

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.
  • This year the coding period we are accepting in pgRouting is may-27 - August 26.
  • 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 this issue 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. "Small" bug fixes can be worked upon anytime to become more familiar with the pgRouting's codebase, if you do that during before the deadline for application, please add it to the proposal (and to the issue you create bellow). PR attempts that are not approved, for whatever reason, are also valid for inclusion into your proposal.

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

# Title Duration Description
1 GRAPH C++ Boost graph algorithms 175 hours Implement 1 boost graph function
2 GRAPH C++ Boost graph algorithms 350 hours Implement 2 boost graph functions

Note 175/350 hours are based on previous programs. This will be updated once we know the official hours for the program.

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. Dont forget to complete the pgRouting application requirements. When a task is missing by the deadline of the application, the application will not be processed.

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 and 2

GRAPH C++ Boost graph algorithms (175/350 hours)

From Boost Graph 1.56 which is the official minimum version since v3.2. In section 22 (Algorithms), there is a list of algorithms from where:

  • Sparse Matrix Ordering Algorithms
  • Graph Metrics
  • and many more sections
    Have algorithms not yet been implemented on pgRouting

For the proposal choose one algorithm (175 hours) or two algorithms (350 hours) that are not yet implemented in pgRouting.

The proposal must include:

  • All requirements from GSoC
  • All requirements from OSGeo
  • The details of the algorithm need to have
    • Section: Testing data
    • Section: Proposed Documentation

Consider that the expected products at the end of GSoC are:

  • Self Documented Code
  • User's Documentation
  • Simple pgtap tests

Section: testing data

The section must have the following statements

  • Link to the Boost example
  • CREATE
  • INSERT
  • SELECT
  • A drawing representing the created graph (can be hand made as Graphs do not have geometries)

That will allow mentors to test data

Section: Proposed Documentation

Try to make it look like a pgRouting function documentation

Notes

Normally the Boost algorithms come with an example, base your proposal on that example's graph Example:

From You would need to CREATE TABLE foo ... and INSERT INTO foo ... a PostgreSQL/pgRouting representation of the graph in the example (remember that on C/C++ counting start from 0, but on PostgreSQL counting start from 1)

      Pair edges[14] = { Pair(0,3), //a-d    in PostgreSQL -> (1,4)
                     Pair(0,5),  //a-f
                     Pair(1,2),  //b-c
...
                     Pair(5,7),  //f-h
                     Pair(6,7) }; //g-h

Then test that the query can be executed and give a result with pgr_dijkstra:

SELECT * FROM pgr_kingOrdering('SELECT * FROM foo', 1, 7);